λDSA Learning Hubpart of DSA Atlas

Binary Search Trees

Intermediate~3h · 7 lessons10 practice problems

The ordering invariant — left < node < right — and the O(h) search/insert/delete, validation, kth-smallest, and floor/ceiling operations it unlocks.

0 of 7 lessons checked off

Introduction

What it is

  • A binary search tree is a binary tree with a global ordering rule: EVERY value in a node's left subtree is smaller, and EVERY value in its right subtree is larger.
  • 'Global' is the operative word — each node constrains its whole subtree, not just its children. That's what makes validation subtler than it looks.

Why it matters

  • The BST is 'binary search, made insertable': O(h) lookup like a sorted array, but with O(h) insert/delete instead of O(n) shifting.
  • It's also the ordered structure: min, max, floor, ceiling, successor, range queries — everything a hash map cannot do.

How it works

  • Search follows one root-to-leaf path: smaller → go left, larger → go right. Insert lands at the first empty slot on that path.
  • Delete has three cases: leaf (unlink), one child (splice), two children (replace with inorder successor, delete it from the right subtree).
  • Balance is everything: h = log n when balanced, n when built from sorted input. Self-balancing variants (AVL, red-black) exist precisely to guarantee the log.

Where it's used

  • Language standard libraries' ordered maps (C++ std::map, Java TreeMap) are red-black BSTs; database indexes use the B-tree generalisation; schedulers pick nearest deadlines via ordered structures.

In interviews

  • Validate BST, kth smallest (inorder), LCA-in-BST (with ordering shortcuts), insert/delete, BST from sorted array, floor/ceiling, and 'range sum of BST'.
Analogy: A well-run library: fiction left wing, non-fiction right wing, and the same rule inside every room. Any book is a short sequence of left/right decisions away — unless someone shelved everything in one long corridor (the unbalanced worst case).

Interactive diagram

The ordering property routes the new value down one path to its unique empty slot.

147631314108
Insert 5

Start at the root. At every node go left if 5 is smaller, right if larger — the BST ordering property decides the entire path.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. The BST property (and its global reach)

    Subtree-wide bounds, not parent-child comparisons.

    20 min
  2. Search and insert

    One path, O(h); duplicates policy.

    20 min
  3. Min, max, floor, ceiling, successor

    Leftmost/rightmost walks; best-so-far tracking.

    25 min
  4. Delete (three cases)

    Leaf, one child, two children via inorder successor.

    30 min
  5. Validate a BST

    Range-narrowing (or inorder monotonicity) — not child checks.

    20 min
  6. Kth smallest and inorder

    Sorted iteration with early exit.

    15 min
  7. Balanced BSTs and building from sorted arrays

    Middle-as-root recursion; why AVL/red-black exist.

    25 min

Operations

Search

Binary search over pointers: each comparison discards a whole subtree.

Search
def search(root, target):    """Node holding target, or None. O(h)."""    node = root    while node:        if target == node.val:            return node        node = node.left if target < node.val else node.right    return None
Time: O(h): O(log n) balanced, O(n) degenerateSpace: O(1) iterative

Edge cases

  • Empty tree → None.
  • Target at root: immediate.
  • Absent target: the walk falls off a leaf.

Common mistakes

  • Checking only children instead of following one path.
  • Quoting O(log n) without the 'if balanced' qualifier.

Insert

Search for the value; attach a new leaf where the search falls off the tree.

147631314108
Insert 5

Start at the root. At every node go left if 5 is smaller, right if larger — the BST ordering property decides the entire path.

def insert(root, val):    """Insert val, returning the (possibly new) root. O(h)."""    if root is None:        return TreeNode(val)    if val < root.val:        root.left = insert(root.left, val)    elif val > root.val:        root.right = insert(root.right, val)    # val == root.val: ignore (no-duplicates policy — state yours!)    return root
Time: O(h)Space: O(h) recursive / O(1) iterative

Edge cases

  • Empty tree: the new node IS the root — that's why insert returns the root.
  • Duplicates: pick a policy (ignore, count field, or consistently right) and say it.
  • Sorted insertion order degenerates the tree — mention self-balancing trees.

Common mistakes

  • Forgetting to reassign root.left/right from the recursive call — the new node is created and dropped.
  • Silently sending duplicates left AND claiming strict inequality.

Delete (three cases)

Leaf: unlink. One child: splice it up. Two children: overwrite with the inorder successor's value, then delete that successor from the right subtree.

Delete (three cases)
def delete(root, val):    """Delete val from the BST, returning the new root. O(h)."""    if root is None:        return None    if val < root.val:        root.left = delete(root.left, val)    elif val > root.val:        root.right = delete(root.right, val)    else:                                   # found it        if root.left is None:               # 0 or 1 child            return root.right        if root.right is None:            return root.left        successor = root.right              # 2 children:        while successor.left:               # min of right subtree            successor = successor.left        root.val = successor.val            # overwrite value...        root.right = delete(root.right, successor.val)  # ...delete donor    return root
Time: O(h)Space: O(h)

Edge cases

  • Deleting the root with two children — handled uniformly by the successor swap.
  • Successor has no left child by construction, so its deletion hits an easy case.
  • Value absent: tree returned unchanged.

Common mistakes

  • Replacing with an arbitrary child instead of the inorder successor/predecessor, breaking the ordering for the whole subtree.
  • Deleting the successor from the wrong subtree (it lives in root.RIGHT).

Validate a BST

Carry (low, high) bounds downward: each node must fit its window and narrows it for its children. Child-only checks are the famous wrong answer.

Validate a BST
def is_valid_bst(root) -> bool:    """Range-narrowing validation. O(n) time, O(h) space."""    def valid(node, low: float, high: float) -> bool:        if node is None:            return True        if not (low < node.val < high):            return False        return (valid(node.left, low, node.val) and                valid(node.right, node.val, high))    return valid(root, float("-inf"), float("inf"))
Time: O(n)Space: O(h)

Edge cases

  • The trap tree: 5 → (3, 7 with 7's left child 4). Child checks pass; the global rule fails (4 < 5 sits in 5's right subtree).
  • Equal values: strict < means duplicates are invalid — align with the problem.
  • int limits: use ±inf, not INT_MIN/MAX literals.

Common mistakes

  • Comparing only node vs its children — the single most famous wrong answer in interviews.
  • Non-strict comparisons accepting duplicates the problem forbids.

Kth smallest

Inorder traversal visits BST values in sorted order; stop at the kth visit.

Kth smallest
def kth_smallest(root, k: int) -> int:    """Inorder with early exit. O(h + k) time, O(h) space."""    stack: list = []    node = root    while node or stack:        while node:            stack.append(node)            node = node.left        node = stack.pop()        k -= 1        if k == 0:            return node.val        node = node.right    raise ValueError("k exceeds tree size")
Time: O(h + k)Space: O(h)

Edge cases

  • k = 1 is the minimum (leftmost node).
  • k > size must raise — decide the contract.
  • Frequent queries with mutations → augment nodes with subtree sizes for O(h) per query (say it as the follow-up answer).

Common mistakes

  • Collecting the FULL inorder list first (O(n) space) when early exit was the point.
  • Decrementing k at push time instead of visit time.

Complexity analysis

OperationBestAverageWorstSpace
Search / insert / deleteO(log n)O(log n)*O(n)O(h)
Min / maxO(1)O(h)O(n)O(1)
Inorder (full)O(n)O(n)O(n)O(h)
ValidateO(n)O(n)O(n)O(h)
Self-balancing (AVL/red-black)O(log n)O(log n)O(log n)O(n)

*Average assumes random insertion order. Sorted input without rebalancing is the O(n) trap — always mention it.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Balanced BST from a sorted array (middle-as-root)
from typing import Optionalclass TreeNode:    def __init__(self, val: int = 0, left=None, right=None):        self.val, self.left, self.right = val, left, rightdef sorted_array_to_bst(nums: list[int]) -> Optional[TreeNode]:    """Height-balanced BST from ascending values. O(n) time, O(log n) stack."""    def build(lo: int, hi: int) -> Optional[TreeNode]:        if lo > hi:            return None        mid = (lo + hi) // 2            # middle keeps both sides equal        node = TreeNode(nums[mid])        node.left = build(lo, mid - 1)        node.right = build(mid + 1, hi)

What interviewers expect you to know

What interviewers expect you to know

  • The property is SUBTREE-wide — and the validation question is designed to catch child-only checkers.
  • Inorder = sorted, and its consequences: validation by monotonicity, kth smallest, two-sum-in-BST.
  • All costs are O(h); say 'log n if balanced, n if degenerate' every time.
  • Delete's two-children case via inorder successor.

Classic follow-ups

  • "LCA in a BST specifically?" — walk from the root: both smaller → left, both larger → right, else split point. O(h), no recursion needed.
  • "What keeps h at log n in production?" — AVL/red-black rotations; know the guarantee, not the rotation mechanics.
  • "Duplicates?" — pick a policy (disallow, count field, or all-right) and apply it consistently.
  • "Why B-trees in databases?" — fan-out matched to disk pages; a BST generalisation, one sentence suffices.

How to talk about BSTs

  • Anchor on the invariant: 'everything left is smaller — so discarding the right subtree is safe.' Every operation is a corollary.
  • When asked to design with ordering requirements (floor, range, nearest), say 'ordered structure — BST family' before coding anything.

Common mistakes

Child-only validation

Checking node vs children passes trees that violate the GLOBAL rule. Carry (low, high) bounds or verify inorder monotonicity.

O(log n) stated unconditionally

Without self-balancing, sorted insertions produce a linked list: O(n). The qualifier is mandatory.

Delete case 3 shortcuts

Promoting a random child instead of the inorder successor breaks ordering invisibly — until some later search misses.

Dropped reassignment on insert/delete

root.left = insert(root.left, v) — without the assignment, recursive versions mutate nothing.

Duplicates unhandled

Strict inequalities with silently-dropped equals, or duplicates sent both ways on different calls — decide once, out loud.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (4)

Medium (4)

Hard (2)

Topic quiz

5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Code output1. Is this tree a valid BST? 5 → left 3, right 7; 7's left child is 4.
  2. Complexity2. Inserting 1, 2, 3, …, n in order into an empty (non-self-balancing) BST gives total cost…
  3. Concept3. Deleting a node with two children, you replace its value with…
  4. Scenario4. Find the LCA of 4 and 7 in a BST rooted at 8 → 3 → (1, 6 → (4, 7)). What's the O(h) logic?
  5. Concept5. Which query is a BST fundamentally better at than a hash map?
0 of 5 answered

Frequently asked questions

Do I need to implement AVL rotations for interviews?

Almost never. You need the WHY (guaranteeing h = log n) and the vocabulary (rotations restore balance after insert/delete). Implementations are asked only in specialised roles.

BST vs heap — both are binary trees, when do I use which?

BST: full ordering — search, floor/ceiling, range, sorted iteration. Heap: only min OR max matters, with O(1) peek and cheap push/pop. If you never need 'find arbitrary key', the heap is simpler and faster.

How are duplicates normally handled?

Interview default: assume distinct (say it). Otherwise: a count field per node is cleanest; consistently-right insertion also works but skews the tree under heavy repetition.

Summary & cheat sheet

Key takeaways

  • The BST rule is subtree-global; validation must carry bounds.
  • Everything costs O(h) — balance decides between log n and n.
  • Inorder = sorted: validation, kth smallest, and range queries fall out.
  • Delete = three cases; two children means inorder-successor swap.
  • Sorted array → balanced BST: middle as root, recurse.

Formulas & cheat sheet

  • min = leftmost node; max = rightmost
  • successor(x): min of right subtree, else the first left-turn ancestor
  • balanced build: root = middle of the sorted range

Interview checklist

  • I can code search, insert, and full three-case delete.
  • I can validate with range narrowing and explain the trap tree.
  • I can do kth-smallest with early-exit inorder.
  • I always qualify O(log n) with 'if balanced'.