LESSON 04 OF 08Validate a BST
0% learnt
VALIDATE BINARY SEARCH TREE · RECURSIVE BOUNDS
What valid range does root 8 receive?
The root has no ancestors, so no finite lower or upper bound exists yet.
RULE TO APPLYLeft child inherits (min, parent); right child inherits (parent, max).
LIVE ALGORITHM STATE8 is valid, so its value becomes a boundary for both children.
ALLOWED RANGE
−∞< 8 <+∞
LESSON 041 / 2
REAL INTERVIEW PROBLEMCheck every value against all of its ancestors.
Given a binary tree, decide whether it is a valid binary search tree: every value in a left subtree must be smaller, and every value in a right subtree must be larger.
INPUT[8, 3, 10, null, null, 6, 14]OUTPUTfalse
WHAT YOU WILL DOChoose the correct (min, max) range for each child and reject the first node outside that range.