Validate Binary Search Tree - Video Solutions

Problem Overview: You’re given the root of a binary tree and need to verify whether it satisfies the rules of a Binary Search Tree (BST). Every node must follow the constraint left subtree < node < right subtree, and this rule must hold for every node in the tree.

Approach 1: Recursive In-Order Traversal (O(n) time, O(h) space)

A key property of a valid BST is that an in-order traversal visits nodes in strictly increasing order. Traverse the tree using recursion: visit the left subtree, process the current node, then visit the right subtree. While traversing, track the value of the previously visited node. If the current node’s value is less than or equal to the previous value, the BST property is violated and the tree is invalid.

This approach works because binary search trees naturally produce sorted output during in-order traversal. The recursion depth depends on the tree height, so the space complexity is O(h), where h is the height of the tree. In balanced trees this is O(log n), but it becomes O(n) in the worst case of a skewed tree. The time complexity remains O(n) because each node is visited exactly once.

Approach 2: Iterative In-Order Traversal (O(n) time, O(h) space)

This version performs the same in-order traversal but replaces recursion with an explicit stack. Start at the root and repeatedly push nodes while moving left until you reach a null node. Pop from the stack, process the node, then move to its right child. During each visit, compare the current value with the previously visited value to ensure the sequence remains strictly increasing.

The iterative approach avoids recursion and gives you more control over the traversal process. It uses a stack to simulate the call stack typically used in depth-first search. Time complexity is still O(n) since every node is pushed and popped once. Space complexity remains O(h) due to the stack storing nodes along the current path from the root to a leaf.

Both approaches rely on the structural property of tree traversal rather than explicitly checking value ranges for every subtree. The sorted in-order sequence provides a simple and reliable validation mechanism.

Recommended for interviews: Recursive in-order traversal is the most common solution interviewers expect because it clearly demonstrates understanding of BST properties and DFS traversal. The iterative version is equally efficient and shows stronger control over stack-based traversal, which can stand out in more advanced interviews.