Binary Search Tree

A binary search tree (BST) is a Binary Tree augmented with an ordering invariant: for every node v, every key in v’s left subtree is strictly less than v.key, and every key in v’s right subtree is strictly greater. This single invariant turns search, insertion, and deletion into O(h) operations where h is the tree’s height — Θ(log n) for balanced trees, Θ(n) for degenerate (chain-shaped) ones. The BST is the conceptual ancestor of every self-balancing tree (AVL Tree, Red-Black Tree, B-trees, splay trees, treaps), and an in-order traversal of any BST yields its keys in sorted order — a property exploited by half the BST interview questions.

1. Intuition — The Phone Book That Splits Itself

Imagine a magical phone book that, instead of being one long sorted list, is organized as a tree. The first page (root) holds one name — say “Mason.” Every page in the left half of the book holds a name alphabetically before “Mason” (e.g., “Adams,” “Klein”); every page in the right half holds a name after (“Patel,” “Zhang”). This same rule applies recursively inside each half: each subtree’s root splits its remaining names into earlier-than-it and later-than-it halves.

To look up “Klein,” start at “Mason” — Klein < Mason, go left. The left subtree’s root might be “Garcia” — Klein > Garcia, go right. The right subtree’s root might be “Klein” — found. You’ve located the entry in three comparisons rather than scanning a list.

Each comparison cuts the search space roughly in half (assuming a balanced tree), giving Θ(log n) lookup — the same asymptotic cost as Binary Search on a sorted array, but with the additional benefit of supporting insertions and deletions without shifting elements. The catch, and the entire reason the next 60 years of tree-data-structure research exists, is that insertions and deletions can unbalance the tree. An adversarial sequence (inserting keys in sorted order) produces a degenerate right-leaning chain in which “looking up Klein” becomes a linear scan again. Self-balancing BSTs (§7.1) restore the balance proactively to keep h = O(log n).

2. The BST Invariant — Stated Carefully

For every node v in the tree:

∀ k ∈ keys(left_subtree(v)):    k < v.key
∀ k ∈ keys(right_subtree(v)):   k > v.key

The strict inequality version disallows duplicates; some BST variants use ≤ on one side and allow duplicates by convention (e.g., always go left on ties). Throughout this note we use the strict version — duplicates are stored separately or counted in a node-attached counter.

A subtle but critical point: the invariant is about all descendants, not just immediate children. The common buggy “validate BST” check (§10.1) confuses these two. The correct mental model is “every node’s entire left subtree is strictly less than the node, and every node’s entire right subtree is strictly greater.”

3. Tiny Worked Example

Insert keys 5, 3, 8, 1, 4, 7, 9 into an initially empty BST in that order. Walking through:

5 → root.
3 < 5 → goes to root’s left → becomes left child of 5.
8 > 5 → goes right → right child of 5.
1 < 5 → 1 < 3 → goes left of 3 → left child of 3.
4 < 5 → 4 > 3 → goes right of 3 → right child of 3.
7 > 5 → 7 < 8 → goes left of 8 → left child of 8.
9 > 5 → 9 > 8 → goes right of 8 → right child of 8.

Final tree:

              5
            /   \
           3     8
          / \   / \
         1   4 7   9

In-order traversal (left, root, right) — by Tree Traversals: 1, 3, 4, 5, 7, 8, 9 — sorted ascending. This is a property of every BST and is the algorithmic backbone of LC 230 (k-th smallest), LC 99 (recover BST), and many others.

Now suppose the same keys had been inserted in sorted order (1, 3, 4, 5, 7, 8, 9):

A degenerate right-leaning chain — height n − 1, search cost O(n). Same set of keys, same invariant, drastically different performance. The BST’s behavior depends entirely on insertion order, which is precisely why self-balancing variants are necessary in any setting where the input order isn’t trusted.

4. Operations

4.1 Search

search(node, key):
    if node == null:        return null
    if key == node.key:     return node
    if key < node.key:      return search(node.left,  key)
    else:                   return search(node.right, key)

Each step descends one level, so search costs O(h). On a balanced BST h = Θ(log n); on a degenerate one h = Θ(n).

4.2 Insert

Insertion is structurally the same descent as search; the new node becomes the leaf at the position where the search would have terminated unsuccessfully.

insert(node, key):
    if node == null:        return new Node(key)
    if key < node.key:      node.left  = insert(node.left,  key)
    elif key > node.key:    node.right = insert(node.right, key)
    # key == node.key: duplicate — choose policy (skip, count, etc.)
    return node

O(h) time, O(h) recursion-stack space. The new node is always inserted as a leaf in a plain BST — there is never a need to restructure an existing node’s children. (Self-balancing BSTs perform additional rotations on the way back up the recursion to restore their stricter invariants — see AVL Tree and Red-Black Tree.)

4.3 Delete — The Three Cases

Deletion is the only structurally interesting operation. There are three cases for the node z being deleted, in increasing order of complexity.

Case 1 — z is a leaf. Just snip it off (set its parent’s child pointer to null).

Case 2 — z has exactly one child. Promote the child: replace z in the tree with its sole child. The BST invariant is preserved automatically because the child’s entire subtree was already on the correct side of z’s former position.

Case 3 — z has two children. This is the case that matters. We can’t just “promote” one child — that would leave the other subtree dangling. Instead, find z’s in-order successor y — the smallest key in z’s right subtree (i.e., the leftmost descendant of z.right). Crucially, y has at most one child (it cannot have a left child by construction — if it did, that left child would be smaller and thus be the leftmost). So:

Copy y.key into z (preserving z’s position in the tree).
Recursively delete the original y from z’s right subtree — and y is now a Case-1 or Case-2 deletion.

The in-order predecessor (largest key in z’s left subtree) works equally well; the choice between successor and predecessor is arbitrary, though always picking the same side can introduce bias and increase tree height over many deletions (Hibbard 1962 first analyzed this; the long-term effect is that pure-BST deletions tend to “drift” the tree’s shape — a known weakness fixed only by self-balancing variants).

delete(node, key):
    if node == null: return null
    if key < node.key:
        node.left  = delete(node.left,  key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:                                       # found the node to delete
        if node.left  == null: return node.right    # Case 1 or 2 (no left)
        if node.right == null: return node.left     # Case 2 (no right)
        # Case 3 — two children.
        succ = min_node(node.right)             # in-order successor
        node.key   = succ.key
        node.right = delete(node.right, succ.key)
    return node

min_node(n):
    while n.left != null: n = n.left
    return n

O(h) total: descent to find the node, plus another descent to find/delete the successor (which is also bounded by h).

4.4 Min / Max / Successor / Predecessor

Min: walk left until you can’t.
Max: walk right until you can’t.
In-order successor of v: if v.right exists, it’s the min of v’s right subtree. Otherwise, climb up until you turn from a left child (the parent at that turn is the successor); if no such ancestor, v is the maximum and has no successor.
Predecessor: symmetric.

All O(h).

5. Python Implementation

Using the same Node class as Tree Traversals and Binary Tree:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def bst_search(root, key):
    while root and root.val != key:
        root = root.left if key < root.val else root.right
    return root  # None if not found
 
def bst_insert(root, key):
    if root is None:
        return Node(key)
    if key < root.val:
        root.left  = bst_insert(root.left,  key)
    elif key > root.val:
        root.right = bst_insert(root.right, key)
    return root  # duplicates ignored
 
def bst_min(node):
    while node.left:
        node = node.left
    return node
 
def bst_delete(root, key):
    if root is None:
        return None
    if key < root.val:
        root.left = bst_delete(root.left, key)
    elif key > root.val:
        root.right = bst_delete(root.right, key)
    else:
        # node found
        if root.left is None:  return root.right
        if root.right is None: return root.left
        succ = bst_min(root.right)
        root.val = succ.val
        root.right = bst_delete(root.right, succ.val)
    return root

5.1 Validating a BST — The Recursive Min/Max Bounds Pattern

This is by far the most-asked BST interview question (LC 98). The naive solution looks correct but is wrong; getting it right requires passing bounds down, not just comparing to immediate children:

def is_valid_bst(root):
    def check(node, lo, hi):
        if node is None:
            return True
        if not (lo < node.val < hi):
            return False
        return (check(node.left,  lo, node.val) and
                check(node.right, node.val, hi))
    import math
    return check(root, -math.inf, math.inf)

The bounds tighten as we descend: when we go left from a node whose value is v, every node in that subtree must be strictly less than v (and also less than every “less than” bound inherited from above). The lo bound captures the strongest “must-be-greater-than” constraint, the hi bound captures the strongest “must-be-less-than” constraint, and a node passes iff lo < node.val < hi.

Alternative correct formulation: do an in-order traversal and verify the visited sequence is strictly increasing. This is also O(n) and arguably even cleaner:

def is_valid_bst_inorder(root):
    prev = [-float('inf')]
    def go(node):
        if node is None: return True
        if not go(node.left):    return False
        if node.val <= prev[0]:  return False
        prev[0] = node.val
        return go(node.right)
    return go(root)

Both are valid; in interviews, mentioning both signals depth.

6. Complexity

Operation	Balanced BST	Degenerate BST
Search	`Θ(log n)`	`Θ(n)`
Insert	`Θ(log n)`	`Θ(n)`
Delete	`Θ(log n)`	`Θ(n)`
Min / Max	`Θ(log n)`	`Θ(n)`
Successor / Predecessor	`Θ(log n)` amortized	`Θ(n)`
In-order traversal (full)	`Θ(n)`	`Θ(n)`
Space	`Θ(n)` (one node per key + parent/child pointers)	same

Every per-operation cost is bounded by O(h), where h is the tree’s height. The minimum possible height for n nodes is ⌊log₂ n⌋ (a perfect tree), the maximum is n − 1 (a chain). A random sequence of distinct insertions yields an average height of Θ(log n) (the “random BST” analysis: expected height ≈ 4.31 log n; see Knuth Vol. 3 §6.2.2), but real-world inputs are rarely random — sorted, reverse-sorted, and almost-sorted streams all degenerate.

This sensitivity to input order is the central practical weakness of plain BSTs and the reason production code almost always uses a self-balancing variant: AVL Tree (strict balance, faster lookups), Red-Black Tree (looser balance, faster updates — used in Java’s TreeMap, C++‘s std::map, the Linux kernel rbtree), B-trees (high-fanout, optimized for disk and modern cache hierarchies), splay trees (self-adjusting based on access patterns), or treaps (BST + heap invariant, randomized balancing).

7. Variants and Use Cases

7.1 Self-Balancing BSTs

AVL Tree (planned, gray) — Adelson-Velsky and Landis, 1962. Maintains |height(left) − height(right)| ≤ 1 at every node via single and double rotations after each insert/delete. Lookups are slightly faster than red-black trees due to tighter balance; updates are slightly slower.
Red-Black Tree (planned, gray) — looser balance via node-coloring rules. Used pervasively in production: Linux kernel’s rbtree, Java’s TreeMap and TreeSet, C++‘s std::map/std::set (typically), .NET’s SortedDictionary.
B-trees / B+ trees — branching factor much greater than 2; designed to minimize disk seeks. Foundation of nearly every database index (PostgreSQL, MySQL/InnoDB, SQLite). See B+ Tree (planned, gray).
Splay trees — self-adjusting; recently-accessed keys move toward the root, giving good amortized performance on temporally-clustered access patterns.
Treaps — combine BST invariant on keys with heap invariant on randomly-assigned priorities; rotations driven by priorities yield expected O(log n) depth.

7.2 Use cases

Ordered map / set — when you need sorted iteration and O(log n) insert/delete (as opposed to a Hash Table, which sacrifices ordering for O(1) average operations).
Range queries — find all keys in [lo, hi] by descending from the LCA of lo and hi. Hash tables can’t do this efficiently.
k-th order statistic — augment each node with its subtree size; descend by comparing k to left-subtree size. O(log n) per query in a balanced tree.
Predecessor/successor queries — what’s the largest key < x? Smallest key > x? O(log n).
Database indexes — though usually B-trees rather than BSTs, the conceptual lineage is direct.

8. The In-Order Sortedness Property — Worth Memorizing

For every BST, in-order traversal (left → root → right) yields keys in strictly increasing order. This is the single most-exploited property of BSTs in interviews:

LC 230 — k-th smallest in BST: in-order traversal, return the k-th visited node. Optimization: do it iteratively with an explicit stack and stop early.
LC 538 / 1038 — convert BST to greater-sum tree: reverse in-order traversal (right → root → left), maintain a running sum, replace each node’s value with the sum.
LC 99 — recover BST (two nodes swapped): in-order traversal must be strictly increasing; the two nodes that violate this are the swapped pair.
LC 98 — validate BST: §5.1.

The reason: in-order’s “left, root, right” exactly matches the BST invariant’s “left < root < right.” Recursive expansion: leftmost subtree’s keys (all < root) appear first, then root, then rightmost subtree’s keys (all > root). By induction on subtree size, the sequence is sorted.

9. Pitfalls

9.1 The Validate-BST Two-Child Bug

The bug:

def is_valid_bst_WRONG(root):
    if root is None: 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_bst_WRONG(root.left) and is_valid_bst_WRONG(root.right)

This checks only that each node’s immediate children satisfy the order, not the full subtree. Counterexample:

The buggy check passes — at every node, immediate-child comparisons are fine. But 6 is in 10’s right subtree and 6 < 10, violating the invariant. In-order traversal exposes this: 5, 10, 6, 15, 20 is not sorted.

The fix is the bounds-passing pattern from §5.1 — a node’s validity depends on the entire path from the root, not just its immediate children. This is the single most-asked BST gotcha; senior interviewers expect you to either (a) write the correct bounds version on the first try, or (b) write the buggy version and notice the flaw within seconds when challenged.

9.2 Duplicate Keys

The strict < and > BST invariant disallows duplicates. Real systems handling duplicates either (a) use ≤ on the left and document it, (b) attach a count field to each node and increment it on duplicate insertion (saves memory, complicates deletion), or (c) chain duplicates in a linked list at the matching node. Always clarify the duplicate policy in interviews — it changes both the API and the complexity analysis.

9.3 Hibbard Deletion Bias

Pure-BST deletion that always replaces with the in-order successor (or always with the predecessor) is known (Hibbard 1962, plus a long line of follow-up empirical work) to slowly skew the tree shape over many delete operations, increasing average height beyond the random-BST baseline. In a long-running pure-BST workload with many deletions, the tree gradually degrades. Self-balancing variants don’t have this problem because they actively rebalance.

9.4 Stack Overflow on Recursive Operations Over Skewed Trees

A right-skewed BST has height n. Recursive search/insert/delete will recurse n deep — Python’s default recursion limit is 1000, so trees with more than ~1000 nodes inserted in sorted order will blow the stack. Either iterative implementations or sys.setrecursionlimit are needed; in production you’d use a self-balancing BST and the problem disappears.

9.5 Comparison Operators on Custom Types

Python’s < operator uses __lt__. If your BST stores custom objects, those objects must define a total order via __lt__ (and probably also __eq__). Forgetting this gives TypeError: '<' not supported between instances of 'X' and 'X' on the second insert.

9.6 Floating-Point Keys

Equality on floats is treacherous — 0.1 + 0.2 != 0.3. A BST keyed on floats can develop near-duplicates that the </> checks classify inconsistently. If you must, use a small tolerance comparator or, better, key on a discretized integer.

9.7 The `[[BST]]` Wikilink Resolves Elsewhere

The vault has a separate note named BST.md storing Behavior Sequence Transformer (an Alibaba CTR-ranking neural architecture), unrelated to the data structure. Obsidian resolves wikilinks by filename match before alias match, so [[BST]] in any vault note will jump to the recommender-system note, not this one. To link to the data structure, always use [[Binary Search Tree]]. If you really want to display “BST” as the visible text while linking to the data structure, use the alias-pipe form: [[Binary Search Tree|BST]]. This is a vault-specific quirk introduced by historical filename collision; see feedback_filename_long_form.md in the project memory for the full story.

10. Diagram — A BST and Its In-Order Walk

flowchart TD
    R((5)) --> L((3))
    R --> RR((8))
    L --> LL((1))
    L --> LR((4))
    RR --> RRL((7))
    RR --> RRR((9))

What this diagram shows. The tree from §3 — every left subtree’s keys are strictly less than the parent, every right subtree’s keys are strictly greater. The root is 5. To search for 7: start at 5, 7 > 5 go right to 8, 7 < 8 go left to 7, found in 3 comparisons. To insert 6: same descent as searching for 6 would take — left of 7 (since 6 < 7), arrive at null, insert there. To delete 5 (Case 3): find in-order successor 7 (leftmost descendant of right subtree starting at 8 → go left to 7), copy 7’s value into the root, then delete the original 7 (which is a Case-2 leaf-with-no-children-on-one-side — easy). In-order traversal of the entire tree yields 1, 3, 4, 5, 7, 8, 9 — sorted, the universal BST property.

11. Common Interview Problems

LC #	Problem	Pattern
700	Search in a Binary Search Tree	Plain `bst_search`
701	Insert into a Binary Search Tree	Plain `bst_insert`
450	Delete Node in a BST	Three-cases delete (§4.3)
98	Validate Binary Search Tree	Bounds-passing recursion (§5.1) — the canonical gotcha
230	Kth Smallest Element in a BST	In-order traversal, stop at `k`
538 / 1038	Convert BST to Greater Sum Tree	Reverse in-order with running sum
235	LCA of a BST	Single descent comparing both targets to current node — see Lowest Common Ancestor
99	Recover Binary Search Tree	In-order finds two violations; swap them
108	Convert Sorted Array to BST	Recursively pick midpoint as root (yields balanced tree)
96	Unique Binary Search Trees	Catalan number; counts BST shapes on `n` keys
95	Unique Binary Search Trees II	Generate all such BSTs
173	Binary Search Tree Iterator	In-order iterator with explicit stack
1382	Balance a Binary Search Tree	In-order to sorted array, then build balanced

The pattern recognition: most BST problems are either (a) “exploit in-order = sorted” or (b) “exploit left < node < right to prune one subtree on each comparison.”

12. Open Questions

How adversarial is “real-world” data for plain BSTs? Sorted inserts are common (loading from sorted files, time-series), but most production code uses self-balancing variants by default — so the empirical degradation is rarely observed in the wild.
Is there a clean way to teach BST deletion that doesn’t lean on the “successor swap” trick? Most textbooks present it as a clever-but-arbitrary choice; the symmetry between successor and predecessor is rarely emphasized as much as it should be.
When does a plain BST beat a balanced BST in practice? Almost never for general workloads; possibly for very small n or single-write/many-read scenarios where insertion order is known to be random.

13. See Also

Binary Tree — the underlying structure without the ordering invariant
Tree Traversals — in-order’s sortedness property is the main BST hook
Tree Diameter — works on any binary tree, not BST-specific
Lowest Common Ancestor — has a much faster BST-specific algorithm
Serialize and Deserialize Binary Tree — BST variant can omit null markers
AVL Tree (planned) — self-balancing BST with strict per-node balance
Red-Black Tree (planned) — self-balancing BST used in production stdlibs
B+ Tree (planned) — high-fanout variant for disk-backed indexes
Binary Search — array analogue of BST descent
Hash Table — alternative dictionary structure trading order for O(1) average
Big-O Notation
SWE Interview Preparation MOC

vault

Explorer

Binary Search Tree

Binary Search Tree

1. Intuition — The Phone Book That Splits Itself

2. The BST Invariant — Stated Carefully

3. Tiny Worked Example

4. Operations

4.1 Search

4.2 Insert

4.3 Delete — The Three Cases

4.4 Min / Max / Successor / Predecessor

5. Python Implementation

5.1 Validating a BST — The Recursive Min/Max Bounds Pattern

6. Complexity

7. Variants and Use Cases

7.1 Self-Balancing BSTs

7.2 Use cases

8. The In-Order Sortedness Property — Worth Memorizing

9. Pitfalls

9.1 The Validate-BST Two-Child Bug

9.2 Duplicate Keys

9.3 Hibbard Deletion Bias

9.4 Stack Overflow on Recursive Operations Over Skewed Trees

9.5 Comparison Operators on Custom Types

9.6 Floating-Point Keys

9.7 The `[[BST]]` Wikilink Resolves Elsewhere

10. Diagram — A BST and Its In-Order Walk

11. Common Interview Problems

12. Open Questions

13. See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

Binary Search Tree

Binary Search Tree

1. Intuition — The Phone Book That Splits Itself

2. The BST Invariant — Stated Carefully

3. Tiny Worked Example

4. Operations

4.1 Search

4.2 Insert

4.3 Delete — The Three Cases

4.4 Min / Max / Successor / Predecessor

5. Python Implementation

5.1 Validating a BST — The Recursive Min/Max Bounds Pattern

6. Complexity

7. Variants and Use Cases

7.1 Self-Balancing BSTs

7.2 Use cases

8. The In-Order Sortedness Property — Worth Memorizing

9. Pitfalls

9.1 The Validate-BST Two-Child Bug

9.2 Duplicate Keys

9.3 Hibbard Deletion Bias

9.4 Stack Overflow on Recursive Operations Over Skewed Trees

9.5 Comparison Operators on Custom Types

9.6 Floating-Point Keys

9.7 The [[BST]] Wikilink Resolves Elsewhere

10. Diagram — A BST and Its In-Order Walk

11. Common Interview Problems

12. Open Questions

13. See Also

Graph View

Table of Contents

Backlinks

9.7 The `[[BST]]` Wikilink Resolves Elsewhere