Recursively Validate BST [Java]

Many interview questions deal with Binary Search Trees (BSTs). In this post, I will write a method of validating if a BST is valid.

To understand this algorithm, we need to understand how BSTs work. These are the common properties of a BST:

• The data stored at each node is unique in the tree.
• Every node has either left or right child, or both right and left, except for a leaf node. 
• A leaf node is a node that does not have any children.
• The key of any node is greater than all the keys in the left sub-tree and smaller than all the keys in the right sub-tree.

Let’s get right into the code of validating a BST.

public boolean validateBST(Node root) {
    return _validateBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean _validateBST(Node curr, int min, int max) {
    if(curr.left != null) {
        if(curr.value < min || !_validateBST(curr.left, min, curr.value) {
            return false;
        }
    }

    if(curr.right != null) {
        if(curr.value > max || !_validateBST(curr.right, curr.value, max) {
            return false;
        }
    }

    return true;
}

The runtime of this algorithm is O(n).