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:

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.
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

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

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

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.

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

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.

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"))

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"))

Consider this tree:

text

text

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

The bounds approach catches it: descending right from 55 sets low = 5low = 5, so node 33 fails 5 < 35 < 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 < highlow < 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.

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

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^41 <= number of nodes <= 10^4, -2^31 <= Node.val <= 2^31 - 1-2^31 <= Node.val <= 2^31 - 1.

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

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][10,5,15,null,null,6,20], node 66 is fine relative to 1515 but sits in 1010’s right subtree while being less than 1010. 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

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.

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 kk, return the kkth smallest value (1-indexed).

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

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

Editorial — approach, complexity, follow-ups

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

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

The loop structure is worth internalising: the outer while stack or nodewhile stack or node continues while there is either a node to descend into or an ancestor owed a visit. The inner while nodewhile 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()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 sizesize field (the count of nodes in its subtree). Then kth-smallest is an $O(h)$ descent: compare kk with size(left) + 1size(left) + 1 and go left, stop, or go right with kk reduced. Insert and delete maintain the counts in $O(h)$ .
“kth largest?” Reverse in-order, or size - k + 1size - k + 1th smallest.
“Do it recursively with an early exit?” Possible with a nonlocalnonlocal 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 valval, return the subtree rooted at the node whose value equals valval, or NoneNone if it does not exist.

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

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

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 rootroot as NoneNone, 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)

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

#	Problem	Difficulty	The twist
700	Search in a Binary Search Tree	Easy	Descend by comparison; falling off returns `NoneNone` for free
108	Convert Sorted Array to Binary Search Tree	Easy	Take the middle as root and recurse — balance for free
501	Find Mode in Binary Search Tree	Easy	In-order groups equal values together, so one pass with a run counter
98	Validate Binary Search Tree	Medium	Inherited bounds, not parent comparison
230	Kth Smallest Element in a BST	Medium	Iterative in-order with an early exit
701	Insert into a Binary Search Tree	Medium	The same descent; attach where the walk falls off
450	Delete Node in a BST	Medium	Two children means replace with the in-order successor
173	Binary Search Tree Iterator	Medium	Expose the in-order stack as `next()next()` / `hasNext()hasNext()`
538	Convert BST to Greater Tree	Medium	Reverse in-order with a running sum

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.SortedListsortedcontainers.SortedList` in practice
“Sum of values in a range?”	Pruning	Descend, and skip a subtree entirely when its whole range is outside `[low, high][low, high]`

Edge-case checklist

Single node — valid BST; k = 1k = 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][5,4,6,null,null,3,7] and [10,5,15,null,null,6,20][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 = 1k = 1 and k = nk = n — the ends of the in-order walk.
Target absent (LC 700) — must return NoneNone, 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.

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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

BST Patterns

What you’ll learn

The cue

Fact 1 — in-order is a sorted walk

Fact 2 — descend by comparison

Validation — bounds, not parents

The variant map

Practice — real LeetCode problems

LC 98 — Validate Binary Search Tree · Medium

LC 230 — Kth Smallest Element in a BST · Medium

LC 700 — Search in a Binary Search Tree · Easy

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?