Validate Binary Search Tree

Link: LeetCode - Validate Binary Search Tree

Problem Statement

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.

Examples

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's right child 4 is less than 5 but in the wrong subtree.

Constraints

• The number of nodes in the tree is in the range [1, 10⁴]

• -2³¹ <= Node.val <= 2³¹ - 1

Intuition

We must ensure every node falls within a valid range:

• For a node, all nodes in the left subtree must be < node.val

• All nodes in the right subtree must be > node.val

We use a recursive function that carries valid min and max bounds and enforces this rule.

Approach: Recursive Bound Check

• Use DFS with (min, max) bounds.

• Start with min = -∞ and max = ∞.

• For each node:

  • Check if node.val lies in (min, max)

  • Recursively check:

    • Left child with updated max → (min, node.val)

    • Right child with updated min → (node.val, max)

Java Code

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

    private boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true;

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

        return validate(node.left, min, node.val) &&
               validate(node.right, node.val, max);
    }
}

Note: We use long instead of int for min/max to avoid edge case overflows (Integer.MIN_VALUE, Integer.MAX_VALUE).

Time & Space Complexity

• Time Complexity: O(N)
  Each node is visited once.

• Space Complexity: O(H)
  Due to recursion stack. Worst case H = N (skewed tree), Best case H = log N (balanced tree).

Dry Run

For input:

     5
    / \
   1   4
      / \
     3   6

• At node 5 → valid range (-∞, ∞)

• Left child 1 → valid range (-∞, 5)

• Right child 4 → valid range (5, ∞)

  • But 4 < 5 → violates BST rule → return false

Conclusion

This method efficiently validates the BST property using a range-based DFS approach.
Alternate solutions using inorder traversal (iterative or recursive) are also possible but more error-prone due to tracking state.