Validate Binary Search Tree
Understanding the Problem
We need to check whether a binary tree satisfies the BST property. A tempting shortcut is to check that every node's left child is smaller and right child is larger, but that is not enough. The BST property is not about immediate children. It is about entire subtrees.
Consider the tree [5,4,6,null,null,3,7]. Node 3 is the left child of 6, so 3 < 6 holds locally. But node 3 sits in the right subtree of the root (5), and 3 < 5 violates the BST rule. Every node in the right subtree of 5 must be greater than 5.
Each node in a BST has an allowable range. Moving left from a node tightens the upper bound. Moving right tightens the lower bound. A node is valid only if its value falls within its current range.
Key Constraints:
[1, 10^4]nodes → With up to 10,000 nodes, an O(n) traversal is comfortable. An O(n^2) approach also stays within limits at this size, so we can start there and improve.-2^31 <= Node.val <= 2^31 - 1→ Values span the full 32-bit integer range. A node can equalInteger.MIN_VALUEorInteger.MAX_VALUE, so neither can serve as a sentinel bound. Using them as the initial range would reject a legitimate node whose value matched the bound. We useLong.MIN_VALUE/Long.MAX_VALUEor null-based bounds instead.
Approach 1: Brute Force (Check All Ancestors)
Intuition
The BST property holds at a node only if every value in its left subtree is smaller and every value in its right subtree is larger. We can check that directly: for each node, scan its full left subtree confirming every value is less than the node, then scan its full right subtree confirming every value is greater. Applying this check to every node is correct, but it re-examines the same subtrees repeatedly.
Algorithm
- For each node in the tree, verify that every node in its left subtree has a smaller value.
- For each node in the tree, verify that every node in its right subtree has a larger value.
- If any node violates this, return false.
- If all nodes pass, return true.
Example Walkthrough
Input:
At node 5, check the left subtree (node 1): is every value less than 5? Node 1 is less than 5, so the left side passes. Check the right subtree (nodes 4, 3, 6): is every value greater than 5? Node 4 is the first value scanned, and 4 is not greater than 5. The check on node 5 fails, so the function returns false without examining the remaining nodes.
Code
- Time Complexity: O(n^2). For each node, we potentially traverse its entire subtree to verify values. In a skewed tree, the root checks all n-1 nodes, then its child checks n-2 nodes, and so on.
- Space Complexity: O(n). The recursion stack can go as deep as the height of the tree, which is O(n) for a skewed tree.
The cost comes from redundant work: each node is re-visited many times to verify the same constraints. The next approach checks each node exactly once by carrying the valid range down during the traversal.
Approach 2: Recursive Range Validation (Optimal)
Intuition
Instead of checking upward from each node, we pass valid bounds downward. Every node in a BST must fall within a specific range. The root can be anything, so its range is (-infinity, +infinity). Moving left from a node with value v makes v the new upper bound. Moving right makes v the new lower bound. If a node's value ever falls outside its allowed range, the tree is invalid.
Consider node 3 (left child of 6, which is the right child of 5). By the time we reach it, the bounds have tightened to (5, 6). Since 3 < 5, it is out of range, and the violation surfaces at the node itself.
A node must be greater than every ancestor it sits to the right of, and less than every ancestor it sits to the left of. The range-based approach captures exactly those ancestors: the lower bound is the largest "turn right" ancestor value, and the upper bound is the smallest "turn left" ancestor value. Any other ancestor is already implied by these two, so checking the node against (lower, upper) is equivalent to checking it against every ancestor. That is why one comparison per node replaces the full subtree scan of the brute force.
Algorithm
- Start at the root with the range
(-infinity, +infinity). - Check if the current node's value is within
(lower, upper). If not, return false. - Recurse on the left child with the range
(lower, node.val), the node's value becomes the new upper bound. - Recurse on the right child with the range
(node.val, upper), the node's value becomes the new lower bound. - If both subtrees are valid, return true.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once and do O(1) work per node: two comparisons and two recursive calls.
- Space Complexity: O(n). The recursion stack depth equals the height of the tree. For a balanced tree that's O(log n), but for a skewed tree it's O(n).
The time complexity is already optimal. A different formulation reaches the same bound using a property specific to BSTs: an in-order traversal of a valid BST produces a sorted sequence.
Approach 3: In-Order Traversal
Intuition
An in-order traversal (left, root, right) of a BST visits nodes in strictly ascending order. So if an in-order traversal ever produces a value that is not strictly greater than the value before it, the tree is not a valid BST.
This approach tracks no ranges. It needs a single variable: the value of the last node visited. If the current node's value is less than or equal to that previous value, the tree has a violation.
Algorithm
- Perform an in-order traversal of the tree (left, root, right).
- Keep track of the previously visited node's value.
- At each node, check if the current value is strictly greater than the previous value.
- If not, return false.
- If the traversal completes without violations, return true.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once during the in-order traversal.
- Space Complexity: O(n). The recursion stack depth equals the height of the tree, which is O(n) in the worst case for a skewed tree and O(log n) for a balanced tree.