Trees III — BST Properties

Review boundary and corrected contracts

This series chooses the distinct-key BST convention; duplicates are not universally forbidden by all BST designs. Search and kth-smallest cost depend on height, which can be n without balancing. LCA assumes both queried nodes exist in the same BST.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Internalise the two BST facts that solve nearly every BST problem: inorder gives sorted order, and the constraint is a range inherited from all ancestors rather than a parent-child comparison.

Series: LeetCode — From Basics to Production-Ready · Session 24 / 65 · Phase 1 · Core patterns

Why this session exists

Validate BST catches everyone who checks only parent against child. Pass bounds down.

That single mistake is worth an entire session because of what it reveals. The BST property is usually stated as "left child smaller, right child larger", and that phrasing is actively misleading — it describes a local relationship when the actual invariant is global. Every node must be smaller than every ancestor it descends left from, and larger than every ancestor it descends right from. A tree can satisfy every parent-child comparison and still not be a BST.

Once you see that the constraint is a range inherited down the tree, validation becomes four lines and the trap disappears. And the same reframing pays off elsewhere: searching, inserting, finding the lowest common ancestor, and finding the kth smallest are all applications of "at this node, I know the range my target must lie in."

The second fact — inorder traversal of a BST emits values in sorted order — is the other half. It converts BST problems into array problems you already know how to solve. Kth smallest becomes "the kth element of a sorted sequence". Validation becomes "is this sequence strictly increasing". Two BST problems, one array fact.

Blank-file warm-up

Five minutes, empty file, no notes. Write:

def dfs(node, lo, hi):

Complete it as a full BST validator, and state explicitly what lo and hi are at the initial call and why those values in particular.

Then, separately, write the inorder traversal that returns a list, and state in one sentence what that list looks like for a valid BST.

If you wrote the validator by comparing node.val against node.left.val and node.right.val, that is exactly the trap this session exists for. Keep the code — you will use it as a counterexample in ten minutes.

Pattern anatomy

The shape that summons this pattern: a binary tree where an ordering property is claimed to hold, and the problem depends on it.

The examples use finite integer keys, distinct-key ordering, and an acyclic binary tree. kth_smallest assumes 1 <= k <= n; it does not validate k. lca_bst assumes both node objects belong to the same valid BST.

The BST invariant, stated correctly:

For every node, all values in its left subtree are strictly less than the node, and all values in its right subtree are strictly greater. Not just the immediate children — the entire subtrees.

That "entire subtrees" clause is what turns validation into a range problem. Descending left tightens the upper bound to the current node's value; descending right tightens the lower bound. Each node inherits the intersection of every constraint imposed by its ancestors.

def is_valid_bst(root):
    def dfs(node, lo, hi):
        if not node:
            return True                       # empty subtree is trivially valid
        if not (lo < node.val < hi):           # violates an inherited bound
            return False
        return dfs(node.left, lo, node.val) and dfs(node.right, node.val, hi)
    return dfs(root, float('-inf'), float('inf'))

Read the recursive line carefully. Going left, the upper bound becomes node.val — everything down there must be less than this node — while the lower bound is inherited unchanged. Going right, the lower bound becomes node.val and the upper is inherited. The bounds only ever tighten.

The initial call uses infinities because the root is unconstrained from above or below. Using float('-inf') and float('inf') rather than sentinel integers avoids a real failure: if the tree can contain the minimum or maximum machine integer, an integer sentinel would wrongly reject a valid node.

The inorder view gives a second, equally valid validator:

def is_valid_bst_inorder(root):
    prev = float('-inf')
    stack, node = [], root
    while stack or node:
        while node:                     # descend left as far as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        if node.val <= prev:            # must be STRICTLY increasing
            return False
        prev = node.val
        node = node.right
    return True

This one has an advantage worth mentioning under a tight review: it exits at the first violation without traversing the rest of the tree, and it uses only O(h) space with no recursion. The <= rather than < is what enforces strictness — duplicates are excluded by this lesson's convention.

Kth smallest is the inorder fact applied directly:

def kth_smallest(root, k):
    stack, node = [], root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val             # stop early — no need to finish
        node = node.right

The early exit matters. Collecting the whole inorder list and indexing works, but it is O(n) time and space regardless of how small k is. This version is O(h + k) and stops as soon as it has the answer.

Lowest common ancestor on a BST is where the range view is at its cleanest:

def lca_bst(root, p, q):
    node = root
    while node:
        if p.val < node.val and q.val < node.val:
            node = node.left            # both in the left subtree
        elif p.val > node.val and q.val > node.val:
            node = node.right           # both in the right subtree
        else:
            return node                 # they split here — this is the LCA

No recursion, no parent pointers, O(1) space. The split point is the answer: the first node where one target goes left and the other goes right, or where the node is one of the targets. On a general binary tree the LCA problem needs a full DFS; on a BST the ordering tells you which way to walk.

The cue

How you recognise this from the problem statement:

1. The words "binary search tree" anywhere. Immediately ask two questions: does inorder-gives-sorted solve this, and does the range view solve this. One of them usually does.
2. "Validate", "verify", "is this a valid BST". Range recursion, or inorder with a prev variable. Never parent-child comparison.
3. "Kth smallest", "kth largest", "in sorted order", "convert to sorted list". Inorder, with an early exit if k is small.
4. "Search", "insert", "delete", "closest value", "floor", "ceiling". Range narrowing, O(h) per operation, usually iterative with no extra space.
5. "Lowest common ancestor" plus BST. The walk-down-until-they-split loop. If the problem says only "binary tree", this shortcut does not apply.

The anti-cue: if the tree is not a BST, none of this transfers. And if the problem involves a BST but the operation destroys ordering — say, arbitrary restructuring — you are back to general tree techniques.

Guided solve

Validate Binary Search Tree. Given the root of a binary tree, determine whether it is a valid BST.

Start with the attempt almost everyone makes first, because seeing it fail is the point:

def is_valid_wrong(root):
    if not root:
        return True
    if root.left and root.left.val >= root.val:
        return False
    if root.right and root.right.val <= root.val:
        return False
    return is_valid_wrong(root.left) and is_valid_wrong(root.right)

This checks every parent against its immediate children, recursively. It looks complete. Now the counterexample:

      5
     / \
    1   4
       / \
      3   6

Check node 5: left child 1 is less, right child 4 is... greater? No — 4 is less than 5, so this particular tree is caught. Adjust it so the local checks all pass:

      5
     / \
    1   6
       / \
      3   7

Node 5: left child 1 < 5, right child 6 > 5. Passes. Node 1: no children. Passes. Node 6: left child 3 < 6, right child 7 > 6. Passes. Node 3: no children. Node 7: no children. Every local check passes and the function returns True.

But this is not a BST. Node 3 lives in the right subtree of node 5, so it must be greater than 5. It is not. An inorder traversal gives [1, 5, 3, 6, 7], which is not sorted. Ordinary BST search for 3 goes left from 5, then right from 1 to a missing child, and incorrectly reports absence. The existing 3 is stranded in the wrong subtree. The structure is broken in a way no parent-child comparison can detect.

The fix follows directly from what went wrong. Node 3's violation is against node 5, its grandparent, which it descended right from. So each node must be checked against every ancestor whose subtree it sits in — and rather than tracking a list of ancestors, note that all those constraints collapse into a single interval. Everything in the right subtree of 5 must exceed 5; everything additionally in the left subtree of 6 must be under 6; so node 3's valid range is (5, 6) and its value of 3 fails.

Now trace the correct version on a valid tree:

      5
     / \
    3   8
   / \
  1   4

• dfs(5, -inf, +inf): -inf < 5 < +inf. Recurse left with (-inf, 5), right with (5, +inf).
• dfs(3, -inf, 5): -inf < 3 < 5. Recurse left with (-inf, 3), right with (3, 5).
• dfs(1, -inf, 3): valid. Both children null, both return True.
• dfs(4, 3, 5): 3 < 4 < 5. Valid. This is the node that matters — 4 is checked against both 3 and 5, its parent and grandparent, in one comparison.
• dfs(8, 5, +inf): valid.

All True. And if node 4 were replaced by 6, the check 3 < 6 < 5 fails immediately — caught by the inherited upper bound from the grandparent, which is exactly what the naive version missed.

The bound must be strict on both sides under this lesson's distinct-key convention. Writing lo <= node.val <= hi permits duplicates and would require a different, explicit duplicate-placement contract. This one shows up as a wrong answer only on inputs containing equal values — which the sample cases in these problems typically do include, precisely because it is a known trap.

Solo timed

15 minutes each, timer visible.

• Kth Smallest Element in a BST — iterative inorder with an explicit stack, decrement k on each pop, return the moment it hits zero. Do not build the full list.
• Lowest Common Ancestor of a BST — the iterative walk-down loop. Handle the case where one of the targets is itself the LCA, which the else branch already covers.

If you finish early: write the recursive inorder validator using a nonlocal prev variable, and decide which of the three validators you would write under a tight review and why.

Common failure modes

Comparing only parent to child. The defining mistake of this session. It accepts trees where a deep node violates a distant ancestor.

Non-strict bounds. lo <= val <= hi admits duplicates, contrary to this lesson's strict-key contract. Other BST designs may store multiplicities or specify a duplicate side.

Integer sentinels instead of infinities. Using a very large or very small integer as the initial bound fails when the tree legitimately contains that value. float('-inf') and float('inf') compare correctly against any integer.

Passing the wrong bound down. Going left tightens the upper bound; going right tightens the lower. Swapping them produces a validator that accepts exactly the wrong trees.

Building the entire inorder list for kth smallest. O(n) when O(h + k) is available. Fine for correctness, but the follow-up "what if k is 1 and the tree is huge" has an obvious answer you should reach for unprompted.

Using the general-tree LCA algorithm on a BST. Correct, but it discards the ordering information and costs O(n) instead of O(h). If the problem said BST, use it.

Forgetting that prev must persist across calls in the recursive inorder validator. A local variable resets on every frame. It needs nonlocal, or an instance attribute, or the iterative form.

Myth: A binary search tree is valid if every node is greater than its left child and less than its right child — that is what the definition says.

Why: That is a necessary condition, not a sufficient one. The real invariant is about entire subtrees: every value in the left subtree must be less than the node, not merely the immediate child. The tree with root 5, right child 6, and 6's left child 3 satisfies every parent-child comparison, yet 3 sits in 5's right subtree while being less than 5. Its inorder traversal is [5, 3, 6] — not sorted — and a search for 3 from the root would take the wrong branch. Local checks cannot see constraints imposed by grandparents and above, which is exactly why bounds must be passed down.

Steps 1: Because the BST property constrains entire subtrees rather than immediate children, a node must satisfy an inequality against every ancestor whose subtree contains it, not just its parent.

Steps 2: Because each ancestor contributes either a lower bound (when the node lies in its right subtree) or an upper bound (when it lies in its left subtree), the full set of constraints is an intersection of half-lines — which is a single open interval.

Steps 3: Because that interval can be carried down as two parameters that only ever tighten, checking a node costs one comparison against inherited bounds rather than a walk back up the ancestor chain.

Steps 4: Because an inorder traversal visits left subtree, then node, then right subtree, and the left subtree holds only smaller values, the emitted sequence of a valid BST is strictly increasing — giving an independent validator and a direct route to kth-smallest.

Steps 5: Because at any node the ordering tells you which subtree a target value must lie in, search and LCA reduce to a single downward walk costing O(h) with no backtracking.

Steps 6: Testable prediction: the tree with root 5, right child 6, and 6's left child 3 passes every parent-child comparison but is not a BST. Any validator that accepts it is checking locally, and its inorder traversal [5, 3, 6] proves the violation.

Picture: Every node sits inside a window that its ancestors have narrowed. Step left and the ceiling drops to the parent's value; step right and the floor rises to it. A node is legal only if it fits inside the window it inherited, and the window never widens on the way down.

Trigger: Fires on the words 'binary search tree' — then ask whether inorder-gives-sorted or the inherited-range view solves the problem, because one of them usually does.

Name: Recursive bounds (lo, hi)

Gain: Four lines, obviously correct once the invariant is stated, and it fails fast at the first violating node without needing any traversal state.

Cost: O(h) stack space, and it is easy to swap which bound tightens on which side — a mistake that produces a validator accepting precisely the wrong trees.

Name: Iterative inorder with a prev variable

Gain: No recursion limit, exits at the first out-of-order pair, and it reuses the inorder skeleton you need for kth-smallest anyway. O(h) space with no frames.

Cost: The two nested loops of iterative inorder are noticeably harder to write cold than the recursive version, and the strict-versus-non-strict comparison on prev is a separate trap.

Name: Collect full inorder list, then check sortedness

Gain: Trivially correct and takes thirty seconds to write; useful as a reference implementation to test the other two against.

Cost: O(n) extra space and no early exit — it traverses the entire tree even when the root's immediate left child already violates the property.

Pick: Use recursive bounds when maximum height is comfortably below the runtime's remaining recursion budget. Use iterative inorder for potentially deep skewed trees; failure can occur far below 10^4 nodes. sys.getrecursionlimit() reports the configured limit, not a universal safe input size.

Complexity

Validate BST — Time: O(n), Space: O(h). Every node is visited once and does O(1) comparison work. The recursion holds one frame per node on the current root-to-node path, so space is the height: O(log n) balanced, O(n) skewed. The and short-circuit means a violation in the left subtree skips the right subtree entirely, which is a best-case improvement but does not change the worst-case bound.

Kth Smallest — Time: O(h + k), Space: O(h). After k pops, every pushed node is either one of those k nodes or remains on the stack, which has at most h nodes. Thus pushes plus pops cost O(h + k), even if one individual descent is long. Small k helps when h is also small; a left-skewed tree has h = n and takes O(n) even for k = 1. Worth stating: if the tree is modified frequently and kth-smallest is queried often, augmenting each node with its subtree size gives O(h) per query, and that is the standard follow-up answer.

LCA on a BST — Time: O(h), Space: O(1). A single downward walk with no backtracking and no stack. Compare against the general binary tree LCA, which is O(n) time and O(h) space because it must search both subtrees without ordering information to guide it.

Self-check (answer follows each question).

Q: Give a concrete tree that passes every parent-child comparison but is not a valid BST, and explain the violation.

A: Root 5 with right child 6, and 6 has left child 3. Every parent-child check passes: 6 > 5, and 3 < 6. But 3 sits in the right subtree of 5 and must therefore exceed 5, which it does not. Inorder gives [5, 3, 6], which is not sorted.

Q: When recursing into the left child, which bound changes and to what value?

A: The upper bound becomes the current node's value, since everything in the left subtree must be strictly less than it. The lower bound is inherited unchanged.

Q: Why use float('-inf') and float('inf') rather than large integer sentinels?

A: If the tree legitimately contains the minimum or maximum machine integer, an integer sentinel would compare equal to it and wrongly reject a valid node. The float infinities are strictly outside any integer value.

Q: Why must the bound check be strict on both sides?

A: This lesson chooses distinct keys, so equal values must be rejected. Non-strict bounds would accept duplicates and no longer implement that contract; other BST conventions must define their own duplicate policy.

Q: What is the complexity of finding the kth smallest with early exit, and why is it better than building the full inorder list?

A: O(h + k) time and O(h) auxiliary space, versus O(n) time and output space for the full list. After k pops, at most k + h nodes have been pushed. It improves on scanning all nodes when h + k is much smaller than n, not merely when k is small.

Q: You must support kth-smallest queries on a BST that is frequently inserted into and deleted from. What changes?

A: Augment each node with the size of its subtree, maintained on insert and delete. Then kth-smallest becomes a downward walk: at each node, compare k against left subtree size plus one to decide whether the answer is in the left subtree, is this node, or is in the right subtree with k reduced accordingly. That gives O(h) per query instead of O(h + k), at the cost of O(h) extra work per modification.

Stretch: true

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Validate BST enters today, and grade it on the counterexample rather than the code: if you could not produce a tree that defeats the parent-child validator, log it hint regardless of whether your implementation was correct. Knowing why the naive version fails is what makes the right version memorable.

• The BST property constrains entire subtrees, not immediate children. Parent-child comparison is necessary but not sufficient.

• Every node's constraints from all its ancestors collapse into one open interval — pass (lo, hi) down and check once.

• Left tightens the upper bound, right tightens the lower. Swapping them produces a validator that accepts the wrong trees.

• Inorder traversal of a valid BST is strictly increasing. That fact converts BST problems into array problems.

• Kth smallest with early exit is O(h + k), which can still be O(n) on a skewed tree. Stop when the counter hits zero.

• LCA on a BST is a single downward walk in O(h) and O(1) space — the first node where the targets split is the answer.

Corrective source notes

• Sedgewick and Wayne, Binary Search Trees — whole-subtree strict ordering, subtree counts, and rank selection. Snapshot checked 2026-10-09; the lesson uses one-based k, whereas the source defines zero-based rank.

• CPython v3.14.0 recursion-limit documentation — the limit is runtime configuration, not an input-size guarantee. Checked 2026-10-09.

• Depth First Search - Algorithms for Competitive Programming — DFS explores a graph through recursive or explicit-stack expansion. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.