Suraj_IOI's blog

By Suraj_IOI, history, 7 months ago, In English,

This program checks whether a Binary tree is a BST or not, can someone explain me the working of recursive return statement in the function isBSTUtil

public class BinaryTree {

Node root; 

boolean isBST() 
    return isBSTUtil(root, Integer.MIN_VALUE, 
boolean isBSTUtil(Node node, int min, int max) 
    if (node == null) 
        return true; 

   if ( < min || > max) 
        return false; 

    return (isBSTUtil(node.left, min, && 
            isBSTUtil(node.right,, max)); 

public static void main(String args[]) 
    BinaryTree tree = new BinaryTree(); 
    tree.root = new Node(4); 
    tree.root.left = new Node(2); 
    tree.root.right = new Node(5); 
    tree.root.left.left = new Node(1); 
    tree.root.left.right = new Node(3); 

    if (tree.isBST()) 
        System.out.println("IS BST"); 
        System.out.println("Not a BST"); 

} class Node { int data; Node left, right;

public Node(int item) 
    data = item; 
    left = right = null; 



7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Suraj_IOI (previous revision, new revision, compare).

7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

There is a simple condition to the nodes of a binary search tree. All nodes in the subtree of node.left have to be smaller than, and all nodes in the subtree of node.right have to be bigger than

Now imagine the following scenario: first you go right, and then left. The nodes in the subtree of node.right.left have to be smaller than (as they are part of the subtree of the left child of node.right), and at the same time bigger than (since they are part of the subtree of the right child of node).

Therefore you naturally have a lower and upper bound for each node. They define a interval, in which the value has to be, so that it can be considered to be be a BST.

And this is exactly what the function isBST checks. It iterates over the tree, in the if statement it checks if the current node satisfies the lower and upper bounds min and max, and then recursively checks if all nodes in the subtrees satisfy them as well. And of course the subtrees have to satisfy even stricter conditions, the upper bound of the left subtree is - 1, and the lower bound of the right subtree is + 1.