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