BST Patterns

A binary search tree adds exactly one guarantee to a binary tree:

$\text{every value in the left subtree} < \text{node} < \text{every value in the right subtree}$

That single invariant produces two facts you should reach for automatically:

1. An in-order traversal visits values in sorted order. Any problem phrased in terms of sortedness — kth smallest, validate, find the mode, convert to a sorted list — is an in-order walk.
2. You can discard half the tree at every step. Comparing the target with the current node tells you which subtree to enter, giving $O(h)$ search instead of $O(n)$.

Most BST problems are one of those two sentences with details attached.

What you’ll learn

• Why in-order is the BST traversal, and the iterative version worth memorising.
• Bounds-based validation — and why comparing with the parent is wrong.
• The $O(h)$ descend template for search, insert and delete.
• Why $h$ is $O(\log n)$ only when the tree is balanced, and what that means for your complexity claims.
• Three real LeetCode problems solved in the browser: 98, 230, 700.

The cue

You are looking at a BST pattern when…

• The problem says “binary search tree” and mentions sorted order, kth, rank, median, or mode — 230, 501, 538.
• You must validate the BST property — 98.
• Search, insert or delete a value — 700, 701, 450.
• Converting between a BST and a sorted sequence — 108, 897, 1008.
• Lowest common ancestor in a BST specifically — 235, which is much easier than the general case; see Lowest Common Ancestor.
• A range query — “sum all values in [low, high]” (938), where the ordering lets you prune whole subtrees.

The anti-cue: if the tree is not a BST, none of this applies — go to Tree DFS or Tree BFS.

Visual intuition

Fact 1, seen directly. The in-order walk of a BST comes out sorted — watch the output strip fill in ascending order while the call stack holds the ancestors still owed a visit.

treeIn-order on a BST is a sorted walk — the stack is the ancestors you still owefact 1 · O(n) time, O(h) stack

call stack

5

1def inorder(node, out):2    if node is None:3        return4    inorder(node.left, out)5    out.append(node.val)      # visit6    inorder(node.right, out)

node5stack depth1

enterEnter 5. The recursive call is pushed onto the stack, which is now 1 frame deep.

Play‹›1/22⟲

Stop the trace after k visits and you have LC 230; expose the step button as next() and you have LC 173. Both problems are this picture with a different stopping rule, which is why the iterative form is the one to memorise.

Validation, and why the parent comparison fails. This is LC 98’s second example — every node satisfies its immediate parent, and the tree is still not a BST:

treeLC 98: node 3 satisfies its parent 4 and still breaks the BST propertybounds, not parents

1def is_valid(node, low=-inf, high=+inf):2    if node is None:3        return True4    if not (low < node.val < high):5        return False          # window violated6    return (is_valid(node.left,  low, node.val) and7            is_valid(node.right, node.val, high))

node5low−∞high+∞ok?yes

check5 must lie strictly inside (−∞, +∞) — it does. Recurse, narrowing the window: the left child inherits (−∞, 5) and the right child (5, +∞).

Play‹›1/4⟲

Follow the inherited range down the right branch: descending right from 5 sets low = 5, so node 3 must satisfy 5 < 3 and fails. A check against the immediate parent only sees 3 < 4 and wrongly accepts. The range is inherited from every ancestor, not just one.

Fact 1 — in-order is a sorted walk

inorder_recursive.py

def inorder(root):
    """Yields BST values in ascending order."""
    if not root:
        return
    yield from inorder(root.left)     # everything smaller
    yield root.val                    # then this node
    yield from inorder(root.right)    # then everything larger

The iterative version is the one worth memorising, because it lets you stop early — which is the entire point of LC 230, and the basis of the BST iterator in LC 173.

inorder_iterative.py

def kth_smallest(root, k):
    stack = []
    node = root
 
    while stack or node:
        while node:                   # descend as far left as possible
            stack.append(node)
            node = node.left
 
        node = stack.pop()            # visit -- this is the next smallest
        k -= 1
        if k == 0:
            return node.val           # early exit: no need to finish
 
        node = node.right             # then explore the right subtree
 
    return -1

The stack holds the ancestors you still owe a visit to. Pushing all the way left, then popping, is what produces ascending order.

Why the iterative version matters

Recursion visits all n nodes unless you thread a counter and an early-exit flag through it, which is awkward. The explicit stack lets you simply return after k visits, giving $O(h + k)$ rather than $O(n)$.

For k = 1 on a large tree that is the difference between touching $\log n$ nodes and touching all of them. It is also exactly the structure LC 173 asks you to expose as next() / hasNext().

Fact 2 — descend by comparison

bst_search.py

def search_bst(root, val):
    while root and root.val != val:
        root = root.left if val < root.val else root.right
    return root

$O(h)$ time, $O(1)$ space, and no recursion. Insert is the same descent, with a new node attached where the walk falls off the tree.

$O(h)$ is not $O(\log n)$ unless the tree is balanced

An unbalanced BST degenerates into a linked list. Inserting 1, 2, 3, 4, 5 in order builds a right-leaning chain where every operation is $O(n)$.

So the honest complexity is $O(h)$, which is $O(\log n)$ for a balanced tree and $O(n)$ in the worst case. Saying "$O(\log n)$" unqualified is a claim an interviewer will probe. Self-balancing variants (AVL, red-black) enforce $O(\log n)$ — see Balanced Trees Overview — and Python’s sortedcontainers.SortedList is the practical stand-in when you need guaranteed bounds.

Validation — bounds, not parents

The most instructive BST bug. To validate, each node must fall within a range inherited from all its ancestors, not merely satisfy a comparison with its immediate parent.

validate_bst.py

def is_valid_bst(root):
    def valid(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):          # must fit the INHERITED range
            return False
        return (valid(node.left, low, node.val)     # tighten the upper bound
                and valid(node.right, node.val, high))   # tighten the lower
 
    return valid(root, float("-inf"), float("inf"))

Why comparing with the parent fails

Consider this tree:

text

    5
   / \
  1   4
     / \
    3   6

Every node satisfies its immediate parent: 3 < 4 < 6, and 4 is in 5’s right subtree. But 3 is in the right subtree of 5 and 3 < 5, so the BST property is violated.

The bounds approach catches it: descending right from 5 sets low = 5, so node 3 fails 5 < 3. A parent-only check passes it and returns the wrong answer. This exact tree is LeetCode 98’s second example, and it exists to punish the naive solution.

The alternative: do an in-order traversal and check the sequence is strictly increasing. Equally correct, and some find it easier to justify — it is Fact 1 applied directly.

Note low < node.val < high uses strict inequalities, because LC 98 requires distinct values. If duplicates were allowed you would need to decide which side they live on and relax one bound accordingly.

Dry run

LC 230 — kth_smallest(root, k=3) on [5,3,8,2,4,7,9]. Sorted order is 2 3 4 5 7 8 9, so the answer is 4 — and the point of the trace is how few nodes are touched to get there.

step	action	stack	k
1	descend left: push 5, 3, 2	[5, 3, 2]	3
2	pop and visit 2	[5, 3]	2
3	node = 2.right → None, so pop again	[5, 3]	2
4	visit 3	[5]	1
5	node = 3.right → 4; descend left from 4 (no left child), push 4	[5, 4]	1
6	pop and visit 4, k == 0 → return 4	[5]	0

• Nodes 7, 8 and 9 are never touched. The whole right subtree of the root is untouched, which is exactly what the early exit buys: $O(h + k)$, not $O(n)$. The recursive generator can do this too (yield is lazy), but a plain recursive traversal that appends to a list cannot.
• Node 5 stays on the stack the entire time. The stack is the set of ancestors still owed a visit, and 5 is owed one until everything smaller than it is done. Read that way, “push all the way left, then pop” stops being a trick.
• Step 3 is the case people drop. After visiting 2 there is no right child, so control returns to the outer while with node = None and a non-empty stack — which is precisely why the loop condition is while stack or node and not while node.

LC 98 — validation on [5,1,4,null,null,3,6], the tree that punishes the parent comparison:

node	inherited range	test	result
5	$(-\infty, \infty)$	$-\infty < 5 < \infty$	pass
1	$(-\infty, 5)$	$-\infty < 1 < 5$	pass
4	$(5, \infty)$	$5 < 4$?	fail → False

The recursion stops at node 4 and never reaches 3 or 6. A parent-only check would descend into them, find 3 < 4 < 6, and wrongly return True. Note also which node fails: 4, not 3 — the violation is detected at the highest node whose inherited range excludes it, which is a useful thing to say when asked “which node is wrong?”

Complexity

h is the tree height: $O(\log n)$ balanced, $O(n)$ degenerate.

Operation	Time	Space
Search / insert by comparison	$O(h)$	$O(1)$ iterative
In-order traversal (all values)	$O(n)$	$O(h)$ stack
$k$-th smallest, iterative with early exit	$O(h + k)$	$O(h)$
$k$-th smallest, full traversal into a list	$O(n)$	$O(n)$
Validation (bounds or in-order)	$O(n)$	$O(h)$
Delete	$O(h)$	$O(1)$ iterative
$k$-th smallest with a subtree-size field	$O(h)$	$O(1)$ — the LC 230 follow-up

Never say "$O(\log n)$" unqualified about a BST

Every bound above is in terms of $h$, and $h = n$ for a tree built by inserting sorted data. Say ”$O(h)$, which is $O(\log n)$ if the tree is balanced and $O(n)$ in the worst case” — an interviewer who hears an unqualified $O(\log n)$ will ask for the degenerate case, and the answer is more convincing when you raised it first.

The LC 230 follow-up (“what if the BST is modified often and you need $k$-th smallest frequently?”) is asking for an augmented tree: store a subtree size in each node, maintain it on insert and delete, and the query becomes an $O(h)$ descent instead of an $O(h + k)$ walk.

The variant map

Variant	Which fact	Canonical problem
Validate	Bounds, or in-order is increasing	98
kth smallest / iterator	In-order with early exit	230 · 173
Search	Descend by comparison, $O(h)$	700
Insert	Descend, attach where you fall off	701
Delete	Descend, then replace with in-order successor	450
Sorted array to balanced BST	Recurse on the middle element	108
Range sum / range queries	Descend, pruning subtrees out of range	938
Accumulate from the largest	Reverse in-order (right, node, left)	538
LCA in a BST	Descend until the values split	235

Reverse in-order is worth knowing

Visiting right, node, left walks the BST in descending order. That turns LC 538 (replace each value with the sum of all values greater than or equal to it) into a single traversal carrying a running total — rather than an $O(n^2)$ search per node.

Whenever a BST problem is about “everything greater than”, try the traversal backwards.

Practice — real LeetCode problems

LC 98 — Validate Binary Search Tree · Medium

Problem. Given the root of a binary tree, determine whether it is a valid BST: every node’s value must be strictly greater than all values in its left subtree and strictly less than all values in its right subtree.

Constraints. 1 <= number of nodes <= 10^4, -2^31 <= Node.val <= 2^31 - 1.

Examples. [2,1,3] gives True · [5,1,4,null,null,3,6] gives False (node 3 is in 5’s right subtree but is less than 5)

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Every node must lie strictly inside a range determined by its ancestors. Descending left lowers the ceiling to the current value; descending right raises the floor.

Time $O(n)$ — every node visited once. Space $O(h)$ recursion.

Cases 2, 4 and 5 are all the same trap in different shapes: a node that satisfies its parent but violates a grandparent. In case 5, [10,5,15,null,null,6,20], node 6 is fine relative to 15 but sits in 10’s right subtree while being less than 10. Only an inherited lower bound catches it.

The in-order alternative is equally good and worth mentioning:

python

prev = float("-inf")
for value in inorder(root):
    if value <= prev:
        return False
    prev = value
return True

This is Fact 1 used directly — a valid BST’s in-order traversal is strictly increasing.

On sentinel bounds

float("-inf") / float("inf") are safe in Python because node values are finite integers. In a language where you would reach for INT_MIN / INT_MAX, the constraints here (values spanning the full 32-bit range) mean a node could legitimately equal your sentinel and a <= comparison would wrongly fail. The usual fix is to pass None for “no bound” and check for it, or use the in-order method. It is a good detail to raise unprompted.

Follow-ups you should expect: “Do it iteratively?” — in-order with an explicit stack, comparing consecutive values. “What if duplicates were allowed?” — decide a side and relax that bound to non-strict. “Find the two swapped nodes that broke the BST (LC 99)?” — in-order, and detect the (one or two) descents.

LC 230 — Kth Smallest Element in a BST · Medium

Problem. Given the root of a BST and an integer k, return the kth smallest value (1-indexed).

Constraints. 1 <= k <= number of nodes <= 10^4, 0 <= Node.val <= 10^4.

Examples. [3,1,4,null,2], k = 1 gives 1 · [5,3,6,2,4,null,null,1], k = 3 gives 3

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

In-order traversal of a BST is a sorted walk, so the kth node visited is the kth smallest. The explicit stack lets you stop as soon as you have counted k.

Time $O(h + k)$. Space $O(h)$.

The loop structure is worth internalising: the outer while stack or node continues while there is either a node to descend into or an ancestor owed a visit. The inner while node pushes the entire left spine. That pair is the canonical iterative in-order and it appears again in LC 173 (BST Iterator), where next() is exactly one iteration of this loop.

Follow-ups you should expect:

• “What if the BST is modified often and you need kth smallest repeatedly?” LeetCode asks this directly. Augment each node with a size field (the count of nodes in its subtree). Then kth-smallest is an $O(h)$ descent: compare k with size(left) + 1 and go left, stop, or go right with k reduced. Insert and delete maintain the counts in $O(h)$.
• “kth largest?” Reverse in-order, or size - k + 1th smallest.
• “Do it recursively with an early exit?” Possible with a nonlocal counter and returning a sentinel, but clumsier than the stack.
• “What if it were an unsorted binary tree?” No ordering to exploit — collect all values and use quickselect or a heap.

LC 700 — Search in a Binary Search Tree · Easy

Problem. Given the root of a BST and a value val, return the subtree rooted at the node whose value equals val, or None if it does not exist.

Constraints. 1 <= number of nodes <= 5000, 1 <= Node.val, val <= 10^7.

Examples. [4,2,7,1,3], val = 2 gives the subtree [2,1,3] · [4,2,7,1,3], val = 5 gives None

Why this test prints a serialised tree

The problem returns a node, not a number, so the test serialises the returned subtree into nested tuples (val, left, right) — which lets it check you returned the right node with its children intact, rather than just a matching value.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The BST property means one comparison eliminates an entire subtree. Walk down until you match or fall off the end — and falling off leaves root as None, which is exactly what you must return, so no special case is needed.

Time $O(h)$. Space $O(1)$ iteratively, or $O(h)$ recursively.

Returning a node rather than a boolean is characteristic of these problems, and it is what makes the recursive one-liner tempting:

python

if not root or root.val == val:
    return root
return self.searchBST(root.left if val < root.val else root.right, val)

Equally correct, but $O(h)$ stack space for no benefit. The loop is strictly better here, and choosing it deliberately is the small judgement being tested.

Follow-ups you should expect: “Insert instead (LC 701)?” — the same descent; when you would fall off, attach a new node there. “Delete (LC 450)?” — the genuinely fiddly one: a node with two children is replaced by its in-order successor (leftmost node of the right subtree), then that successor is deleted recursively. “What if the tree is unbalanced?” — $O(h)$ becomes $O(n)$; mention self-balancing trees. “Find the floor/ceiling of a value?” — same descent, remembering the best candidate seen on the way down.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 450 is the one to rehearse

Delete Node in a BST is the only structurally awkward operation, and it comes up often. Three cases once you have found the node:

• No children — return None.
• One child — return that child (splice it in).
• Two children — find the in-order successor (leftmost node of the right subtree), copy its value into this node, then delete the successor from the right subtree. The successor has at most one child by construction, so that recursive delete hits an easy case.

Using the in-order predecessor (rightmost of the left subtree) is equally valid. The reason either works is that the successor is the smallest value still greater than everything in the left subtree — exactly the constraint the slot needs to satisfy.

13 problems

5 easy7 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○108Convert Sorted Array to Binary Search TreeeasyTake the middle as root and recurse -- balance for freeLeetCode Top Interview 150
• ○501Find Mode in Binary Search TreeeasyIn-order groups equal values together, so one pass with a run counter
• ○530Minimum Absolute Difference in BSTeasyLeetCode Top Interview 150
• ○700Search in a Binary Search TreeeasyDescend by comparison; falling off returns `None` for free
• ○897Increasing Order Search Treeeasy
• ○98Validate Binary Search TreemediumInherited bounds, not parent comparisonNeetCode 150Blind 75LeetCode Top Interview 150
• ○173Binary Search Tree IteratormediumExpose the in-order stack as `next()` / `hasNext()`LeetCode Top Interview 150
• ○230Kth Smallest Element in a BSTmediumIterative in-order with an early exitNeetCode 150Blind 75LeetCode Top Interview 150
• ○235Lowest Common Ancestor of a Binary Search TreemediumNeetCode 150Blind 75
• ○450Delete Node in a BSTmediumTwo children means replace with the in-order successor
• ○538Convert BST to Greater Treemedium**Reverse** in-order with a running sum
• ○701Insert into a Binary Search TreemediumThe same descent; attach where the walk falls off
• ○99Recover Binary Search Treehard

Interview follow-ups

They ask	What they’re checking	The answer
“Why in-order?”	The core fact	Left-subtree values all precede the node, which precedes all right-subtree values — so in-order is a sorted walk
“Is it $O(\log n)$?”	Precision	$O(h)$ — $O(\log n)$ only if balanced, $O(n)$ for a degenerate chain
“Why not compare with the parent when validating?”	The classic trap	A node can satisfy its parent and violate a grandparent; bounds must be inherited from all ancestors
“Repeated kth-smallest queries with updates?”	Augmentation	Store subtree sizes in each node; kth-smallest becomes an $O(h)$ descent
“How do you delete a node with two children?”	Whether you have rehearsed it	Replace with the in-order successor, then delete that successor recursively
“How would you keep it balanced?”	Breadth	AVL or red-black rotations; in Python, sortedcontainers.SortedList in practice
“Sum of values in a range?”	Pruning	Descend, and skip a subtree entirely when its whole range is outside [low, high]

Edge-case checklist

• Single node — valid BST; k = 1 returns it.
• Empty tree — most of these guarantee at least one node, but guard anyway.
• Left-only or right-only chain — the $O(h) = O(n)$ case; also the one that breaks naive balance assumptions.
• Node violating a grandparent — [5,4,6,null,null,3,7] and [10,5,15,null,null,6,20]; the reason for bounds.
• Values at the integer extremes — sentinel bounds must not collide with real values.
• k = 1 and k = n — the ends of the in-order walk.
• Target absent (LC 700) — must return None, not raise.
• Duplicates — LC 98 forbids them; if allowed, decide which side they go on and relax that bound.
• Deleting the root — the case that makes LC 450’s return value matter.

Self-check

pch.quizTag BST patterns — self-check

1. Why does validating a BST require inherited bounds rather than a comparison with the parent?

   A Because parents can be null B Because a node must fit a range inherited from every ancestor — in [5,1,4,null,null,3,6], node 3 satisfies its parent 4 but is in 5's right subtree while being smaller than 5 C Because duplicates are allowed D Because the tree may be unbalanced
   pch.quizShowAnswer

   B — Because a node must fit a range inherited from every ancestor — in [5,1,4,null,null,3,6], node 3 satisfies its parent 4 but is in 5's right subtree while being smaller than 5 — That tree is LC 98's second example and exists specifically to fail the parent-only check. The bounds version rejects at node 4, because descending right from 5 sets low = 5.

2. For LC 230 (k-th smallest), what does the iterative in-order walk buy over the recursive one?

   A Lower constant factors B An early exit: you can return after k visits, giving O(h + k) instead of touching all n nodes — and it is the same structure LC 173 asks you to expose as next()/hasNext() C It avoids the O(h) stack D It handles duplicates
   pch.quizShowAnswer

   B — An early exit: you can return after k visits, giving O(h + k) instead of touching all n nodes — and it is the same structure LC 173 asks you to expose as next()/hasNext() — In the dry run, k = 3 on a 7-node tree never touches nodes 7, 8 or 9. A recursive generator is equally lazy; a recursive traversal that appends into a list is not.

3. Why is the loop condition `while stack or node` rather than `while node`?

   A Style B Because after visiting a node with no right child, `node` becomes None while ancestors still owe a visit — the stack is what keeps the walk alive C To handle the empty tree D Because `node` is reassigned inside the loop
   pch.quizShowAnswer

   B — Because after visiting a node with no right child, `node` becomes None while ancestors still owe a visit — the stack is what keeps the walk alive — Step 3 of the dry run is exactly this: after visiting 2 there is no right child, so the outer condition must be satisfied by the non-empty stack alone.

4. What is the honest complexity of BST search?

   A O(log n) B O(h) — which is O(log n) only if the tree is balanced, and O(n) for a tree built by inserting sorted data C O(n) always D O(1) amortised
   pch.quizShowAnswer

   B — O(h) — which is O(log n) only if the tree is balanced, and O(n) for a tree built by inserting sorted data — Inserting 1,2,3,4,5 in order builds a right-leaning chain. Say 'O(h), balanced gives O(log n)' before the interviewer asks for the degenerate case — self-balancing variants or sortedcontainers.SortedList are the fixes.

5. The follow-up to LC 230 is: the BST is modified often and k-th smallest is queried often. What changes?

   A Cache the sorted list and rebuild on each modification B Augment each node with its subtree size, maintain it on insert and delete, then the query is an O(h) descent instead of an O(h + k) walk C Use a heap instead D Nothing — O(h + k) is already optimal
   pch.quizShowAnswer

   B — Augment each node with its subtree size, maintain it on insert and delete, then the query is an O(h) descent instead of an O(h + k) walk — Caching a sorted list makes every modification O(n). The subtree-size field is the intended answer, and it is the same augmentation idea as an order-statistic tree.

6. Which single property makes every BST pattern on this page work?

   A That the tree is balanced B That an in-order traversal yields values in ascending order — so 'sorted array' techniques (two pointers, binary search, adjacent-difference) transfer directly to a BST C That every node has at most two children D That the values are distinct
   pch.quizShowAnswer

   B — That an in-order traversal yields values in ascending order — so 'sorted array' techniques (two pointers, binary search, adjacent-difference) transfer directly to a BST — LC 98, 230, 173, 530 and 501 are all this one fact used differently. When a BST problem looks unfamiliar, ask what the sorted sequence would make obvious.

Recall card

• Cue — the problem says binary search tree, or asks for something ordered (k-th smallest, closest value, range sum, predecessor) in a tree.
• Fact 1 — in-order is a sorted walk. Every sorted-array technique transfers. Use the iterative form so you can stop early.
• Fact 2 — descend by comparison. root = root.left if val < root.val else root.right; $O(h)$ time, $O(1)$ space, no recursion.
• Validation — inherited bounds, not parent comparisons: valid(node, low, high) tightening one side per descent. Or: in-order must be strictly increasing.
• Cost — everything is $O(h)$: $O(\log n)$ balanced, $O(n)$ degenerate. Never say $O(\log n)$ unqualified.
• while stack or node — the stack keeps the walk alive after a node with no right child.
• Follow-up — frequent modifications plus frequent k-th queries → store subtree sizes and descend in $O(h)$.

Recap

• A BST gives two exploitable facts: in-order is a sorted walk, and one comparison discards half the tree.
• Anything about sortedness — kth, mode, validate, convert — is an in-order traversal. Learn the iterative version; the early exit is what makes LC 230 and LC 173 work.
• Validate with inherited bounds, never with parent comparisons. Or check that the in-order sequence is strictly increasing.
• Search, insert and delete are all the same $O(h)$ descent; delete is the only fiddly one (in-order successor for two children).
• Say $O(h)$, and note it is $O(\log n)$ only when balanced.
• Reverse in-order (right, node, left) walks descending — the trick behind LC 538.
• For repeated rank queries under updates, augment nodes with subtree sizes.

Next: Lowest Common Ancestor — the general-tree recursion, and why a BST makes the same problem dramatically easier.