BST · Stage 3 of 3
Range Bounds & BST Validation
Pass (low, high) constraints down recursive calls to verify or construct BSTs
Foundations
So far, every lesson trusted the tree to be a BST. Now, what if you must check that it is one, or build one, and comparing each node with its parent is not enough?
The BST rule covers whole subtrees, not just children: a node deep on the root's left must still be smaller than the root. So pass bounds down the recursion. Each call gets a range (low, high) its node must fall strictly inside; going left, the node's value becomes the new high, and going right, the new low. The root starts with (−∞, ∞), and a node outside its range breaks the rule.
On the balanced tree from nums = [7, 1, 5, 3, 6], 5 gets (−∞, ∞). Its left child 3 gets (−∞, 5) and passes (−∞, 3) to 1; its right child 7 gets (5, ∞) and passes (5, 7) to 6. Every value fits, so the rule holds. A 4 in place of 6 would pass a parent check, 4 < 7, but fail (5, 7).
high at the parent's value, going right raises low. 6 must lie in (5, 7), set by two ancestors, not one parent.Case Scenario
The problem
Validate Binary Search Tree
Return true if root is a valid BST: every value in the left subtree is strictly less than the node, and every value on the right is strictly greater.
- Input
- root = [5, 1, 7, None, None, 4, 8]
- Output
- False
Validate Binary Search Tree asks whether a tree obeys the BST rule everywhere. Comparing each node with its parent is the trap: in root = [5, 1, 7, None, None, 4, 8], 4 is a fine left child of 7, but it sits in 5's right subtree, where every value must exceed 5. Passing (5, 7) down to it catches that, so the answer is False.
The direct approach checks each node against its own children. That passes this tree, since 4 is less than its parent 7, yet the tree is not a BST. A correct brute force lists every value in order and checks that the list strictly increases: right answer, but O(n) extra memory, and it finishes the traversal before it can reject anything.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.