Watch 10 video solutions for Validate Binary Search Tree, a medium level problem involving Tree, Depth-First Search, Binary Search Tree. This walkthrough by NeetCode has 257,702 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
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 value is 5 but its right child's value is 4.
Constraints:
[1, 104].-231 <= Node.val <= 231 - 1Problem Overview: Given the root of a binary tree, determine whether it satisfies the properties of a Binary Search Tree (BST). For every node, all values in the left subtree must be smaller and all values in the right subtree must be larger, and this rule must hold recursively for the entire tree.
Approach 1: Recursive In-Order Traversal (O(n) time, O(h) space)
A valid Binary Search Tree produces a strictly increasing sequence when traversed using in-order traversal (left → node → right). Run a recursive Depth-First Search and track the previously visited node value. During traversal, compare the current node with the previous value; if the current value is not greater, the BST property is violated. This approach works because in-order traversal of a BST naturally sorts values. Time complexity is O(n) since every node is visited once, and space complexity is O(h) from the recursion stack, where h is the height of the tree.
This method is clean and commonly expected in interviews. The recursive structure mirrors the natural definition of a binary tree, making the logic easy to reason about.
Approach 2: Iterative In-Order Traversal with Stack (O(n) time, O(h) space)
The same sorted-order insight can be implemented iteratively using a stack. Instead of recursion, push nodes while traversing left until reaching the smallest element. Pop from the stack, compare the node value with the previously processed value, then move to the right subtree. Each node is pushed and popped once, so the total time complexity remains O(n). The stack stores at most the height of the tree, giving O(h) space complexity.
This approach is useful when recursion depth may be large or when you prefer explicit control over the traversal process. The logic mirrors the recursive solution but replaces the call stack with an explicit stack structure.
Recommended for interviews: Recursive in-order traversal is the fastest way to communicate the core BST insight. It shows you understand how BST ordering relates to traversal. The iterative version demonstrates deeper understanding of traversal mechanics and stack simulation. Interviewers usually accept either, but the recursive solution is the most concise and commonly written on the whiteboard.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive In-Order Traversal | O(n) | O(h) | Cleanest solution. Best for interviews and when recursion depth is manageable. |
| Iterative In-Order Traversal (Stack) | O(n) | O(h) | When avoiding recursion or implementing traversal explicitly using a stack. |