Validate Binary Search Tree

Validate Binary Search Tree

What is this problem about?

The "Validate Binary Search Tree" interview question asks you to determine if a given binary tree is a valid Binary Search Tree (BST). In a valid BST, for every node, all values in its left subtree must be strictly less than the node's value, and all values in its right subtree must be strictly greater than the node's value.

Why is this asked in interviews?

This "Validate Binary Search Tree" coding problem is a classic at companies like Amazon, Microsoft, and Google. It tests your understanding of tree properties and recursive traversal. It specifically targets a common misconception: that simply checking if a node's children are valid is enough (it isn't; you must check the entire subtree range).

Algorithmic pattern used

The primary algorithmic pattern is "Depth-First Search (DFS)" with a recursive "Tree interview pattern." You pass a valid range [min, max] down to each node. For the root, the range is [-infinity, +infinity]. When moving left, the max becomes the current node's value. When moving right, the min becomes the current node's value.

Example explanation

Tree: 5 at root, 3 on left, 7 on right, 4 as right child of 3.

1. Root (5): Range (-inf, +inf). 5 is in range.
2. Move left to 3: Range (-inf, 5). 3 is in range.
3. Move right from 3 to 4: Range (3, 5). 4 is in range.
4. Move right from 5 to 7: Range (5, +inf). 7 is in range.
5. All nodes pass their range checks. Result: Valid BST.

Common mistakes candidates make

A common mistake is only checking node.left.val < node.val < node.right.val. This fails for a tree where a node deep in the left subtree is greater than the root. Another error is using Integer.MIN_VALUE or MAX_VALUE as boundaries, which fails if the tree actually contains those values. Using null or a specialized wrapper to represent infinity is safer.

Interview preparation tip

For the "Validate Binary Search Tree" coding problem, an alternative approach is to perform an In-order traversal. In a valid BST, an in-order traversal should yield values in strictly increasing order. If you encounter a value that is less than or equal to the previous one, the tree is not a valid BST. This is often easier to implement and reason about.