Validate Binary Search Tree (LeetCode 98)
You're handed the root of a binary tree and must judge whether it is a legitimate binary search tree (BST).
A tree only counts as a valid BST when, at every node:
- everything in its left subtree is strictly smaller than the node's own key,
- everything in its right subtree is strictly larger than the node's own key, and
- both of those subtrees are themselves valid BSTs.
Worked Examples
root = [2,1,3]true1 sits left of 2 and is smaller; 3 sits right of 2 and is larger.root = [5,1,4,null,null,3,6]false5, but its right child is 4. Everything in the right subtree must be greater than 5, so the tree is not a valid BST.⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[1, 104].-231 <= Node.val <= 231 - 1
Core Insight
Narrowing valid range bounds during recursion ensures ancestor constraints are never violated.
Real-World Scenario & Production Applications
B-Tree database index invariant verification, sorted symbol table integrity checking.
Subproblems & Recurrence Decomposition3 Phases
A valid BST requires every node value to satisfy strict open bounds: low < node.val < high. Root starts with (-inf, +inf).
def validate(node, low, high):
if not node:
return True
if not (low < node.val < high):
return FalseStep-by-Step Execution Trace Table
| Node | Valid Interval (low, high) | Node.val in Interval? | Decision |
|---|---|---|---|
| 2 (root) | (-inf, +inf) | -inf < 2 < +inf (True) | Valid |
| 1 (left) | (-inf, 2) | -inf < 1 < 2 (True) | Valid |
| 3 (right) | (2, +inf) | 2 < 3 < +inf (True) | Valid BST |
root = [2,1,3]true| Node | Valid Interval (low, high) | Node.val in Interval? | Decision |
|---|---|---|---|
| 2 (root) | (-inf, +inf) | -inf < 2 < +inf (True) | Valid |
| 1 (left) | (-inf, 2) | -inf < 1 < 2 (True) | Valid |
| 3 (right) | (2, +inf) | 2 < 3 < +inf (True) | Valid BST |
| 1 | def validate(node, low, high): |
| 2 | if not node: |
| 3 | return True |
| 4 | if not (low < node.val < high): |
| 5 | return False |
| 6 | return validate(node.left, low, node.val) and validate(node.right, node.val, high) |
| 7 | return validate(root, float('-inf'), float('inf')) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
"Just check that each node is bigger than its left child and smaller than its right child" is the tempting shortcut — and it's wrong. A node can look locally fine while still violating the BST property against an ancestor several levels up.
📜 The Analogy: A Contract That Gets Narrower With Every Signature
Imagine a legal contract that starts with an unlimited range: "your value can be anything." As it's handed down from the root, every time you step left, the contract gets a new upper limit (this branch must stay below the parent). Every time you step right, it gets a new lower limit (this branch must stay above the parent). By the time the contract reaches a deep node, it's been narrowed by every single ancestor along the way, not just the immediate parent — so a node's real obligation is "obey every constraint every ancestor imposed," not merely "obey your parent."
🔑 The Key Idea in the Code
The left recursive call tightens the upper bound to the current node's value; the right call tightens the lower bound. Each call receives the cumulative range every ancestor has already narrowed — which is exactly why a single local comparison (child vs. immediate parent) isn't enough, but this open-interval range is.
Local child comparison trap: Only verifying
node.left.val < node.val < node.right.vallocally. A node in the right subtree could be smaller than the root ancestor! Pass bounding intervals(low, high)down the recursion.Strict inequality violation: BST definition requires strictly less than and strictly greater than. Allowing
node.val == lowornode.val == highpermits invalid duplicates in standard BSTs.Integer boundary overflow: Initializing
low = -231andhigh = 231 - 1fails when node values equalINT_MINorINT_MAX. Usefloat('-inf')andfloat('inf').
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Binary search tree validation requiring strict global subtree ordering.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: every node in the current subtree must satisfy low < node.val < high.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
if not (low < node.val < high)checks the window from every ancestor; checking onlyleft.val < node.val < right.valaccepts[5, 4, 6, null, null, 3, 7], where the 3 under the 6 breaks the root's rule.Computing both sides before combining (
left_ok = validate(...),right_ok = validate(...), thenreturn left_ok and right_ok) still walks the whole right subtree after the left side has failed.return validate(node.left, low, node.val) and validate(node.right, node.val, high)stops at the first broken bound.Treating an empty subtree as a failure:
Noneis a valid BST, so the base case returnsTrue; returningFalsethere rejects every tree that has a leaf.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use BST Bounds. The BST rule covers whole subtrees, so each node must fit between bounds set by every ancestor, not just its parent. I carry an open window (low, high) down from (-inf, inf): going left caps high at node.val, going right raises low to node.val, and each node checks low < node.val < high, strictly, so duplicates fail. The trap is checking only children: in [5, 4, 6, null, null, 3, 7] every parent and child pair looks fine, but 3 sits in 5's right subtree. Each node is checked once, so
O(N)time, and the recursion is O(H) deep."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: DFS passes the valid range (low, high) to each child. At each node, checks low < node.val < high in O(1) time. Each node visited once.
O(H) Auxiliary
Recursion stack depth equals tree height H.
T(N) = O(N)
Derivation Progression
(L, node.val) for left, (node.val, R) for right
Tightens valid numeric bounds for each subtree.
L < node.val < R
Verifies BST property in constant time.
N node evaluations
Validates tree in linear time.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Call stack depth (log N to N)
O(1) Zero heap allocations
O(1) Boolean return
Boundary Best / Worst Cases
on early invalid root/child violation.
.
on valid BST.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "validate binary search tree", "strictly less than / greater than". The BST rule is about whole subtrees, not pairs of nodes, so each node inherits limits from every ancestor on its path: BST Bounds, an open window carried down, with every node satisfying .
, . Time budget is linear time.
At scale the risk is depth, not the comparison: inserting keys in sorted order builds a chain, and a -node chain is nested validate calls, past CPython's default recursion limit of 1000. Production code raises the limit or walks with an explicit stack of (node, low, high) entries, which keeps the same window per node.
Validate Binary Search Tree (LeetCode 98)
You're handed the root of a binary tree and must judge whether it is a legitimate binary search tree (BST).
A tree only counts as a valid BST when, at every node:
- everything in its left subtree is strictly smaller than the node's own key,
- everything in its right subtree is strictly larger than the node's own key, and
- both of those subtrees are themselves valid BSTs.
Worked Examples
root = [2,1,3]true1 sits left of 2 and is smaller; 3 sits right of 2 and is larger.root = [5,1,4,null,null,3,6]false5, but its right child is 4. Everything in the right subtree must be greater than 5, so the tree is not a valid BST.⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[1, 104].-231 <= Node.val <= 231 - 1
Core Insight
Narrowing valid range bounds during recursion ensures ancestor constraints are never violated.
Real-World Scenario & Production Applications
B-Tree database index invariant verification, sorted symbol table integrity checking.
Subproblems & Recurrence Decomposition3 Phases
A valid BST requires every node value to satisfy strict open bounds: low < node.val < high. Root starts with (-inf, +inf).
def validate(node, low, high):
if not node:
return True
if not (low < node.val < high):
return FalseStep-by-Step Execution Trace Table
| Node | Valid Interval (low, high) | Node.val in Interval? | Decision |
|---|---|---|---|
| 2 (root) | (-inf, +inf) | -inf < 2 < +inf (True) | Valid |
| 1 (left) | (-inf, 2) | -inf < 1 < 2 (True) | Valid |
| 3 (right) | (2, +inf) | 2 < 3 < +inf (True) | Valid BST |
root = [2,1,3]true| Node | Valid Interval (low, high) | Node.val in Interval? | Decision |
|---|---|---|---|
| 2 (root) | (-inf, +inf) | -inf < 2 < +inf (True) | Valid |
| 1 (left) | (-inf, 2) | -inf < 1 < 2 (True) | Valid |
| 3 (right) | (2, +inf) | 2 < 3 < +inf (True) | Valid BST |
| 1 | def validate(node, low, high): |
| 2 | if not node: |
| 3 | return True |
| 4 | if not (low < node.val < high): |
| 5 | return False |
| 6 | return validate(node.left, low, node.val) and validate(node.right, node.val, high) |
| 7 | return validate(root, float('-inf'), float('inf')) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
"Just check that each node is bigger than its left child and smaller than its right child" is the tempting shortcut — and it's wrong. A node can look locally fine while still violating the BST property against an ancestor several levels up.
📜 The Analogy: A Contract That Gets Narrower With Every Signature
Imagine a legal contract that starts with an unlimited range: "your value can be anything." As it's handed down from the root, every time you step left, the contract gets a new upper limit (this branch must stay below the parent). Every time you step right, it gets a new lower limit (this branch must stay above the parent). By the time the contract reaches a deep node, it's been narrowed by every single ancestor along the way, not just the immediate parent — so a node's real obligation is "obey every constraint every ancestor imposed," not merely "obey your parent."
🔑 The Key Idea in the Code
The left recursive call tightens the upper bound to the current node's value; the right call tightens the lower bound. Each call receives the cumulative range every ancestor has already narrowed — which is exactly why a single local comparison (child vs. immediate parent) isn't enough, but this open-interval range is.
Local child comparison trap: Only verifying
node.left.val < node.val < node.right.vallocally. A node in the right subtree could be smaller than the root ancestor! Pass bounding intervals(low, high)down the recursion.Strict inequality violation: BST definition requires strictly less than and strictly greater than. Allowing
node.val == lowornode.val == highpermits invalid duplicates in standard BSTs.Integer boundary overflow: Initializing
low = -231andhigh = 231 - 1fails when node values equalINT_MINorINT_MAX. Usefloat('-inf')andfloat('inf').
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Binary search tree validation requiring strict global subtree ordering.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: every node in the current subtree must satisfy low < node.val < high.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
if not (low < node.val < high)checks the window from every ancestor; checking onlyleft.val < node.val < right.valaccepts[5, 4, 6, null, null, 3, 7], where the 3 under the 6 breaks the root's rule.Computing both sides before combining (
left_ok = validate(...),right_ok = validate(...), thenreturn left_ok and right_ok) still walks the whole right subtree after the left side has failed.return validate(node.left, low, node.val) and validate(node.right, node.val, high)stops at the first broken bound.Treating an empty subtree as a failure:
Noneis a valid BST, so the base case returnsTrue; returningFalsethere rejects every tree that has a leaf.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use BST Bounds. The BST rule covers whole subtrees, so each node must fit between bounds set by every ancestor, not just its parent. I carry an open window (low, high) down from (-inf, inf): going left caps high at node.val, going right raises low to node.val, and each node checks low < node.val < high, strictly, so duplicates fail. The trap is checking only children: in [5, 4, 6, null, null, 3, 7] every parent and child pair looks fine, but 3 sits in 5's right subtree. Each node is checked once, so
O(N)time, and the recursion is O(H) deep."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: DFS passes the valid range (low, high) to each child. At each node, checks low < node.val < high in O(1) time. Each node visited once.
O(H) Auxiliary
Recursion stack depth equals tree height H.
T(N) = O(N)
Derivation Progression
(L, node.val) for left, (node.val, R) for right
Tightens valid numeric bounds for each subtree.
L < node.val < R
Verifies BST property in constant time.
N node evaluations
Validates tree in linear time.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Call stack depth (log N to N)
O(1) Zero heap allocations
O(1) Boolean return
Boundary Best / Worst Cases
on early invalid root/child violation.
.
on valid BST.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "validate binary search tree", "strictly less than / greater than". The BST rule is about whole subtrees, not pairs of nodes, so each node inherits limits from every ancestor on its path: BST Bounds, an open window carried down, with every node satisfying .
, . Time budget is linear time.
At scale the risk is depth, not the comparison: inserting keys in sorted order builds a chain, and a -node chain is nested validate calls, past CPython's default recursion limit of 1000. Production code raises the limit or walks with an explicit stack of (node, low, high) entries, which keeps the same window per node.