Suraj_IOI's blog

Recursion Under if-loop
By Suraj_IOI, history, 6 years 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, 
                           Integer.MAX_VALUE); 
} 
boolean isBSTUtil(Node node, int min, int max) 
{ 
    if (node == null) 
        return true; 

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

    return (isBSTUtil(node.left, min, node.data-1) && 
            isBSTUtil(node.right, node.data+1, 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"); 
    else
        System.out.println("Not a BST"); 
}

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

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

}

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years 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 node.data, and all nodes in the subtree of node.right have to be bigger than node.data.

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 node.right.data (as they are part of the subtree of the left child of node.right), and at the same time bigger than node.data (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 node.data 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 node.data - 1, and the lower bound of the right subtree is node.data + 1.

→ Reply