CODEWITHSUNDEEP
javadebuggingrecursiontreebinary-search-tree
fnaticRC ggwp
fnaticRC ggwp

Reputation: 1003

Understanding Java Recursion code to check if tree is a valid Binary Search Tree

I am studying data structures in Java (Trees, currently). I have a function that determines if a tree is a valid BST. The function functions correctly but I am not able to understand how it is running. The function goes as :

//call from Main method 
boolean isBST = theTree.isValidBST(theTree.root);
System.out.println("isBST??" +isBST);

//actual method body
public boolean isValidBST(Node root) {
    return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);    
}

public boolean isValidBST(Node focusNode, int min, int max){
    if(focusNode==null) 
        return true;
     System.out.println("Comparing "+focusNode.key+ " with "+min+" min value ");
     System.out.println("Comparing "+focusNode.key+ " with "+max+" max value ");
        if(focusNode.key <= min || focusNode.key >= max)
            return false;

    return isValidBST(focusNode.leftChild, min, focusNode.key) && isValidBST(focusNode.rightChild, focusNode.key, max);
}

My actual tree looks like this : enter image description here

The output of above function is : 

Comparing 50 with -2147483648 min value 
Comparing 50 with 2147483647 max value 
Comparing 25 with -2147483648 min value 
Comparing 25 with 50 max value 
Comparing 15 with -2147483648 min value 
Comparing 15 with 25 max value 
Comparing 30 with 25 min value 
Comparing 30 with 50 max value 
Comparing 75 with 50 min value 
Comparing 75 with 2147483647 max value 
Comparing 85 with 75 min value 
Comparing 85 with 2147483647 max value 
isBST??true

Now cananyone explain how the execution is going on here ? How are teh nested(recursive) calls made to the function ? I lack a lot in understanding recursive function calls. If anyone can make me understand this code, I shall be able to solve many recursion probelms related to the trees. Looking out for some help. Thanks a lot.

Upvotes: 1

Views: 629

Answers (1)

Spencer Brett
Spencer Brett

Reputation: 236

In order for a Tree to be a Binary Search Tree (BST), it must satisfy these conditions.

  1. Each node must have a key or associated value.
  2. Each node must have at most two distinguished sub-trees, commonly denoted left and right.
  3. The key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.

Specifically, this function is validating that the tree satisfies the third condition already assuming the first two are true. This recursive function traverses the Tree until it hits a leaf node and makes sure that each child node is either less than its parent (if it is a left child) or greater than its parent (if it is a right child). There are two base case conditions (if you don't know what a base case is you need to read up more on recursion).

  1. The function has terminated at a leaf node (the node is null).
  2. The function has invalidated the aforementioned condition.

The tree traversal occurs on this line:

return isValidBST(focusNode.leftChild, min, focusNode.key) && isValidBST(focusNode.rightChild, focusNode.key, max);

Each node must validate its left and right sub tree before the node itself can be considered valid.

Upvotes: 2

Related Questions