Validate Binary Search Tree

Problem Statement

LeetCode-98: Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Approach

A straightforward approach that comes to mind is to compare the root node with the left and right child nodes. If the root node is greater than the left child node and less than the right child node, then the tree is a valid BST. We can recursively check the left and right subtrees to determine if they are valid BSTs.

But this approach is not correct. Consider the following tree:

    5
   / \
  1   8
     / \
    4   9

The tree above is not a valid BST even though in respective subtrees, the root node is greater than the left child node and less than the right child node.

The correct approach is to keep track of the range of values that the current node should fall into.

• For the root node, the range is (-inf, inf).
• For the left child node, the range is (-inf, root.val),
• and for the right child node, the range is (root.val, inf).

This is because the left child node should have a value less than the root node, and the right child node should have a value greater than the root node. We can recursively check the left and right subtrees with the updated range.

Implementation

Here is a Java implementation of the approach:

public boolean isValidBST(TreeNode root) {
    return check(root, Long.MAX_VALUE, Long.MIN_VALUE);
}

private boolean check(TreeNode root, long max, long min){
    if(null == root){
        return true;
    }

    // If the current node value is not within the range, return false
    if(root.val >= max || root.val <= min){
        return false;
    }

    // Check the left and right subtrees with the updated range
    // For the left subtree, the range is (min, root.val)
    // i.e. the maximum value that any node in the left subtree can have should
    // be less than the root value

    // For the right subtree, the range is (root.val, max)
    // i.e. the minimum value that any node in the right subtree can have should
    // be greater than the root value
    return check(root.left, root.val, min) && check(root.right, max, root.val);
}

Complexity Analysis

The overall time complexity of the approach is $O(N)$, where $N$ is the number of nodes in the binary tree. We are visiting each node once.