L24 · Trees III — BST Properties

Series: LeetCode — From Basics to Interview-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 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 in an interview: 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 not allowed in the standard definition.

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, and a search for 3 starting at the root would go right to 6, then left to 3 and find it — but a search for 3 in a correct BST would go left from 5. 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.

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 in an interview 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. The standard definition requires strict inequality on both sides.

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.

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). The initial descent to the leftmost node costs O(h). After that, each of the k pops does O(1) work plus at most one descent, and the total descent work across the whole traversal is bounded by the number of edges, so the amortised cost per pop is O(1). This is strictly better than the O(n) full-inorder approach whenever k is small. 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.

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.