Check given binary tree is binary search tree (java/ recursive/ examples)

• Given a binary tree, check whether given binary tree is binary search tree or not.
  • Traverse the binary tree using depth first search (DFS) recursive algorithm.
• What is binary search tree (bst) ?
  • Left child of binary tree is less than its parent node
    • e.g. Node B is less than Node A (Fig 1).
  • Right child of binary tree is greater than its parent node.
    • e.g. Node C is greater than Node A (Fig 1).
  • Binary Tree will be binary search tree, if above properties holds good for every node in a binary tree.

Algorithm: check given binary tree is binary search tree in java

• Node A is root of binary tree.
• Node B is less than Node A
  • Check left & right child of node B
    • Node D is less than Node B
    • Node E is greater than Node E
• Node C is greater the Node A
  • Similarly verify the properties with children of Node C.
• Above algorithm should suffice to check whether binary tree is BST.

Optimized algorithm to check given binary tree is binary search tree

• At every non leaf node, check the possible value ranges
• Node A can have value ranging from Integer.MIN_VALUE to  Integer.Max_Value
  • So, there is no restriction of value for root node of BST.
• What are the possible values of Node B?
  • Node B is left child of Root A
  • Node B can have any value that is less than A (i.e. <50)
• What are the possible values of Node C?
  • Node C is right child of Root A
  • Node C can have any value that is greater than A (i.e. >50)
• What will be possible value for Node F?
  • As F is left child Node C and it can have value less than Node C (i.e. <60)
  • Can we know what is minimum it can have?
  • Yes, It can hold all values greater than Node A and less than Node C
    • Node F > Node A & Node F < Node C
• What will be possible value range for Node E?
  • Similar to Node F, Its range will be:Node E > Node B and Node E < Node A

Examples: check binary tree is binary search tree using recursive algorithm

Example 1: Check given binary tree is binary search tree

The above binary tree is binary search tree, as every node within its specified range.

Example 2: Given binary tree is not binary search tree.

• We have modified value Node H of Fig 2. We changed it to 90.
• We can see that Node H is less than Node F.
  • It should be greater than Node A value (as it on right side A).
• Its violation of BST properties.
• Binary tree is not a BST.

Time Complexity of algorithm is O(n).

Program – Check given binary tree is binary search tree in java

1.) IsBST Class:

• IsBST class check whether given binary tree is binary search tree or not.
• Traverse the binary tree using recursive algorithm.

package org.learn.Question;

import org.learn.PrepareTree.Node;

public class IsBST {
	public static boolean isBST(Node node) {
		return IsBST.isBST(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}

	private static boolean isBST(Node node, int min, int max) {
		if (node == null)
			return true;

		if (node.data < min || node.data > max)
			return false;

		boolean isLeft = isBST(node.left, min, node.data);
		if (!isLeft)
			return isLeft;

		boolean isRight = isBST(node.right, node.data, max);
		if (!isRight)
			return isRight;

		return true;
	}
}

2.) Node Class:

• Node class representing the node of a binary tree.

package org.learn.PrepareTree;

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}
	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App class:

• We are creating binary tree in a main method.
• We are calling method of IsBST class, to check given binary tree is binary search tree (or not).

package org.learn.Client;

import org.learn.PrepareTree.Node;
import org.learn.Question.IsBST;

public class App 
{
    public static void main( String[] args )
    {  
       //root level 0
       Node A = Node.createNode(100);
       //Level 1
       Node B = Node.createNode(50);
       Node C = Node.createNode(150);
       //Level 2
       Node D = Node.createNode(25);
       Node E = Node.createNode(75);
       Node F = Node.createNode(125);
       Node G = Node.createNode(175);
       //Level 3
       Node H = Node.createNode(120);
       Node I = Node.createNode(140);
       Node J = Node.createNode(160);
       Node K = Node.createNode(190);
             
       //connect Level 0 and 1
       A.left  = B;
       A.right = C;
       //connect level 1 and level 2
       B.left  = D;
       B.right = E;
       C.left  = F;
       C.right = G;
       //Connect level 2 and level 3
       F.left  = H;
       F.right = I;
       G.left  = J;
       G.right = K;
         
       if(IsBST.isBST(A)) {
    	   System.out.println("Binary Tree is binary search tree");;
       } else {
    	   System.out.println("Binary Tree is not binary search tree");
       }
       
       Node H1 = Node.createNode(90);
       F.left  = H1;
       if(IsBST.isBST(A)) {
    	   System.out.println("Binary Tree is binary search tree");;
       } else {
    	   System.out.println("Binary Tree is not binary search tree");
       }
    }
}

Output – check given binary tree is BST in java (Fig 2 & Fig 3)

Binary Tree is binary search tree
Binary Tree is not binary search tree

Download  code – Check binary tree is binary search tree recursive algorithm