BST Validation
Carry valid min and max boundaries so every node respects the whole BST, not just its parent.
0 of 3 problems solved
BST Validation
Carry valid min and max boundaries so every node respects the whole BST, not just its parent.
- •Does every node have to stay within a valid min and max range?
- •Is checking only parent-child values enough?
- •Should I pass boundaries down recursively?
Validate BST is where people learn that local checks are not enough. A node is not valid just because it is bigger than its left child and smaller than its right child. It must also respect every ancestor's limits. The clean solution is to carry a valid min and max boundary down the recursion.
BST validation is about global boundaries, not just parent-child comparisons.
- 1Each node receives a valid lower bound and upper bound.
- 2If the node value is outside those bounds, fail immediately.
- 3The left child gets the current node as its new upper bound.
- 4The right child gets the current node as its new lower bound.
Checking only direct children misses cases where a deep node violates an older ancestor's rule.
Search in a Binary Search Tree
If value equals node, return it. If less, go left. If greater, go right. Same as binary search but following tree pointers.
Recover Binary Search Tree
In-order DFS reveals the two swapped nodes because they break ascending order. First anomaly is the node larger than its successor; second is the node smaller than its predecessor.