Check if a tree is a Binary Search Tree (BST)

Problem

Given a binary tree, write an efficient algorithm to validate that the tree is a Binary Search Tree (BST). A tree is a BST if for every node in the tree the left child is smaller than the current node and the right child is bigger than the current node.

Approach

The key to find the solution to this problem is understand that it’s not enough to check at each node if the left and right child satisfy the BST property. Consider for instance the following tree:

       5
      / \
     4   6
    / \
   2   7

This is clearly not a BST but if we naively checked each node separately then the algorithm would return a positive result. A better approach would be to make sure that for each node the maximum value on the left subtree is lower than the current node and the minimum value on the right subtree is greater than the current node. A brute force solution would take O(n^2) runtime since for each node we would need to scan all the left and right sub-trees.

Solution

The intuition to design an efficient algorithm is to keep track of the max and min values allowed for each node and push down this information at every recursive call. We can assume that the initial values are the max and min integer values allowed in your language of choice. This solutions takes O(n) runtime since we need to scan each node only once and O(h) space for the recursion, which in the worst case is O(n).

static boolean isBST(BTNode root) {
    return validate(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

static boolean validate(BTNode BTNode, int min, int max) {
    if(BTNode == null) {
        return true;
    }

    if(BTNode.data > max || BTNode.data < min) {
        return false;
    }

    return validate(BTNode.left, min, BTNode.data) & validate(BTNode.right, BTNode.data, max);
}