Trees & Heaps

1 · Tree terminology basic

Open your file explorer and look at it for a second. A folder holds files and other folders; each of those can hold more; and there's exactly one way up from any file to the top. You've been navigating a tree your whole computing life without naming it. The same shape is the org chart at work (one CEO, everyone has one manager), the reply threads under a comment, the DOM behind every web page, and — the reason it's in this chapter — the structure that gives you O(log n) search when a flat list would cost you O(n).

Here's the everyday analogy that makes every term below click: think of a family tree drawn upside-down. One ancestor sits at the top (that's the root). Lines fan downward to descendants (children), and the people at the very bottom with nobody below them are the "youngest generation" (leaves). The whole point of the arrangement is that from any person there's exactly one path back up to the top — no loops, no shortcuts.

Now the precise vocabulary, which will stick because you have the picture: a tree is a set of nodes with one root and no cycles; every node has exactly one parent (except the root) and any number of children. Nodes with no children are leaves. The height is the longest root-to-leaf path; depth is a node's distance from the root. A tree is balanced when no leaf is much deeper than another — that's what keeps operations at O(log n) instead of degrading to O(n).

The common trip-up worth naming now: people casually say "tree" and picture something neat and bushy, but a tree can also be a sad, lopsided chain where each node has a single child — technically still a tree, but with height O(n), which throws away everything trees are good for. The word that separates the fast tree from the slow one is balanced. Almost every hard idea later in this chapter (self-balancing BSTs, heaps being "complete") is really just machinery to defend that one property. Keep asking of any tree you meet: is it short and bushy, or tall and stringy? — because that, not the number of nodes, decides its cost.

2 · Binary trees basic → intermediate

Picture the game "20 Questions." You're trying to guess what someone is thinking, and every question you ask has only two answers — yes or no. "Is it an animal?" No. "Is it man-made?" Yes. Each answer cuts the world of possibilities roughly in half, and after a handful of two-way splits you've zeroed in. That branching-in-twos shape is a binary tree, and the reason it matters is exactly that halving: a structure where every step is a two-way choice can reach any of n items in about log₂ n steps instead of n.

The formal definition is deliberately simple: a binary tree gives each node at most two children (left, right). It's the linked structure from D2 with two pointers instead of one — and recursion (D3) is the natural way to process it. That last point deserves emphasis. A binary tree is defined recursively — a node is a value plus a left binary tree plus a right binary tree — so the cleanest code to process one is almost always recursive too. When you want a tree's height, you don't write a loop with a counter; you say "my height is one more than my taller child's height," and let the function call itself down to the empty branches. The shape of the code mirrors the shape of the data.

The gotcha that catches beginners: the base case. Every recursion on a tree bottoms out at an empty spot — a child that is None — and if you forget to handle that, your function walks off the end of the tree and crashes with a null-reference error (or infinite recursion). Notice in the lab below that height returns -1 for an empty subtree, a small deliberate choice that makes a lone leaf come out as height 0. Getting the base case and its exact value right is 90% of writing correct tree code; the recursive step is usually the easy part. And do not confuse a plain binary tree with the binary search tree of §4 — a binary tree imposes no ordering on the values, it's just "at most two children"; the searchable version adds a rule we'll meet shortly.

pythonclass TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# height and node-count are naturally recursive
def height(node):
    if node is None:
        return -1                       # empty subtree: height -1 so a leaf is 0
    return 1 + max(height(node.left), height(node.right))

def count(node):
    if node is None:
        return 0
    return 1 + count(node.left) + count(node.right)

#        4              build:  4
#       / \                    / \
#      2   6                  2   6
root = TreeNode(4, TreeNode(2), TreeNode(6))
print(height(root), count(root))       # 1 3

3 · Traversals — the four ways to visit every node intermediate

Imagine you've inherited a rambling old house and have to inventory every room. You could pick a door and walk as far down that wing as it goes, into the deepest closet, before ever backtracking to try another door — that's depth-first. Or you could inventory everything on the ground floor first, then everything on the first floor, then the second — sweeping level by level — that's breadth-first. Both visit every room exactly once; they just disagree about the order. Getting the traversal order wrong is a real bug source: an agent that walks a nested task tree in the wrong order can run a child step before the parent that sets it up, and you'll spend an afternoon wondering why the state is empty.

So the plain-language version first: you visit a tree either depth-first (go deep before wide — uses the call stack / an explicit stack) or breadth-first (level by level — uses a queue, the deque from D2). That pairing is not a coincidence and it's worth burning in: depth-first goes with a stack, breadth-first goes with a queue. A stack (last-in-first-out) keeps diving into the most recent branch; a queue (first-in-first-out) hands out nodes in the fair, level-by-level order they were discovered. If you ever forget which structure a traversal needs, ask whether you want to go deep (stack) or wide (queue).

Depth-first then splits into three flavours, and here is the single idea that unlocks all of them: the three orders differ only in when you record the current node relative to its two children — before them (pre-order), between them (in-order), or after them (post-order). Same walk, one line moved. Each has a job it's best at: pre-order copies a tree top-down (you make the parent before its children); post-order tears one down or evaluates it bottom-up (you finish the children before the parent); and in-order has a small miracle we'll lean on again and again — on a search tree it emits the values in sorted order. The common mistake is to memorize the three output strings by rote; don't. Learn the one rule about where the "visit" step sits, and you can regenerate any of them on the spot.

pythonfrom collections import deque

def preorder(node, out):      # node, then children — good for copying a tree
    if node:
        out.append(node.value)
        preorder(node.left, out); preorder(node.right, out)

def inorder(node, out):       # left, node, right — sorted order for a BST!
    if node:
        inorder(node.left, out)
        out.append(node.value)
        inorder(node.right, out)

def postorder(node, out):     # children, then node — good for deleting/eval
    if node:
        postorder(node.left, out); postorder(node.right, out)
        out.append(node.value)

def level_order(root):        # BFS — a queue, level by level
    out, q = [], deque([root] if root else [])
    while q:
        node = q.popleft()
        out.append(node.value)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return out

4 · Binary search tree (BST) advanced

Think about how you find a word in a physical dictionary. You don't start at "aardvark" and read forward — you flop it open near the middle, see you've landed on "M", and instantly know your word "ferret" is in the first half, so you ignore the entire back of the book. Flip again into that half, halve again, and in a dozen jumps you're on the page. You just did a O(log n) search by hand. A binary search tree is that dictionary frozen into a data structure: every node is a "middle" you compare against, and each comparison lets you throw away a whole half of what's left.

Formally, a BST enforces an ordering invariant: for every node, all values in its left subtree are smaller and all in its right are larger. That invariant means search is like binary search (D6) but on a tree — at each node you go left or right, halving the remaining nodes: O(log n) when balanced. This is what elevates a plain binary tree (§2, which imposed no order) into a searchable index. The rule isn't decoration; it's a promise that pays a dividend on every lookup: because a value can live in only one place consistent with the ordering, "search," "insert," and "find where this goes" are all the same downward walk — compare, step left or right, repeat. And it gives you sorted order for free, since the in-order traversal from §3 reads a BST out smallest-to-largest.

Now the phrase you must attach to the words "when balanced," because it is the whole catch: that beautiful O(log n) only holds if the tree is short and bushy. Feed a plain BST values that are already sorted — 1, 2, 3, 4, 5 — and every new value is larger than everything before it, so it hangs off to the right, and to the right, and to the right, until your "tree" is a straight vertical chain of height n. At that point search is O(n) — you've built an over-engineered linked list. This degeneration is the single most important gotcha of the section, it's a favourite interview trap, and it's precisely the problem that self-balancing trees in §5 exist to solve. As you read the insert code below, keep one eye on what shape the inserts produce, not just whether they land in the right spot.

pythonclass BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return TreeNode(value)          # found the empty spot
        if value < node.value:
            node.left = self._insert(node.left, value)   # go left
        elif value > node.value:
            node.right = self._insert(node.right, value) # go right
        return node                        # duplicates ignored

    def search(self, value):
        node = self.root
        while node:
            if value == node.value: return True
            node = node.left if value < node.value else node.right
        return False                       # O(log n) balanced, O(n) worst

t = BST()
for v in [5, 3, 7, 1, 4]: t.insert(v)
out = []; inorder(t.root, out)
print(out)                                 # [1, 3, 4, 5, 7] — sorted!

5 · Balanced trees — AVL & red-black expert (concept) advanced

Here's the failure the last section set up, now made real. You build a BST-backed index for a service, test it with shuffled sample data, and it flies — O(log n) lookups, everyone's happy. Then it goes live against a data source that happens to arrive in sorted order (timestamps, auto-increment IDs, an alphabetized import), and every insert hangs off the same side. Your tree quietly collapses into a chain of height n, lookups slow to O(n), and the dashboard that was green in staging is red in production. Nothing in your code changed — only the order of the data did. This is why nobody ships a plain BST as a serious index.

The fix is a self-balancing BST: a tree that performs rotations after insert/delete to keep the height at O(log n), guaranteeing fast operations regardless of insertion order. A rotation is worth picturing concretely — it's a small, local rearrangement, like grabbing a lopsided mobile hanging from one string and re-hooking it from its middle so it hangs level. Crucially, a rotation preserves the left < node < right ordering (so search still works) while shortening the tree (so search stays fast). The tree does this bookkeeping automatically on every write, spending a little extra work per insert to buy a permanent guarantee that the structure never degenerates.

Two famous variants make different trade-offs, and the distinction is a classic interview question. An AVL tree keeps itself strictly balanced (sibling subtree heights differ by at most 1), so lookups are as fast as possible but writes may trigger more rotations. A red-black tree balances more loosely using per-node "colours" and a handful of rules, doing fewer rotations per write — which is why it's the default under most standard-library ordered maps (Java's TreeMap, C++ std::map) and even the Linux kernel scheduler. The common misconception to head off: you almost never hand-implement these in application code, and — surprisingly — Python ships no built-in balanced-tree type at all. That's not an oversight to code around blindly; the tip at the end of this section shows the two things you actually reach for (bisect and sortedcontainers). Know what the guarantees are so you can recognize when you need them; know what Python gives you so you don't reinvent a red-black tree at 2am.

• AVL tree: strictly balanced (heights of the two child subtrees differ by ≤1). Faster lookups, more rotations on write.
• Red-black tree: loosely balanced via node "colors" + rules. Fewer rotations, so faster writes — the usual choice for library maps (Java's TreeMap, C++ std::map, the Linux kernel scheduler).

python# A right rotation fixes a left-heavy node. (Left rotation is the mirror.)
#        y                x
#       / \              / \
#      x   C    ->      A   y
#     / \                  / \
#    A   B                B   C
def rotate_right(y):
    x = y.left
    y.left = x.right      # B moves under y
    x.right = y           # y becomes x's right child
    return x               # x is the new subtree root

6 · Binary heap — from scratch advanced

You met this problem back in D2 and it's worth re-feeling. You need to keep pulling out the "most important" item from a growing pile — the top-scoring RAG chunk, the nearest node in Dijkstra, the next task by priority. If you keep the pile sorted, finding the best is instant but every insert costs O(n) to slot into place. If you keep it unsorted, inserts are cheap but finding the best is an O(n) scan every single time. Either way one operation is always slow — and if you're doing this in a loop over millions of items, that slow operation is what melts your service. The binary heap is the structure that refuses to pick a loser: it makes both "add an item" and "remove the best" cost only O(log n).

The trick is to give up on total order and keep just enough of it. A binary heap is a complete binary tree with the heap property: every parent ≤ its children (a min-heap). Read that carefully — it does not say the tree is sorted. Siblings can be in any order; a node deep on the left can be larger than one high on the right. The only promise is parent-below-child, everywhere. That looseness is exactly what makes it cheap to maintain, and it's still strong enough to guarantee the one thing you care about: the global minimum has nowhere to hide but the very top. Think of a corporate hierarchy where every manager earns less than everyone they manage — you don't know the exact pay ranking of two people in different departments, but you know the lowest-paid person of all is the person at the very top.

The detail that surprises everyone, and the reason this section exists: a heap is a tree with no tree nodes and no pointers. Because the tree is complete (every level full, filling left-to-right), you can lay it flat in an ordinary array and compute family relationships with arithmetic — the children of index i live at 2i+1 and 2i+2, its parent at (i−1)//2. No left/right attributes, no allocation per node, just index math on a list. That's the whole reason Python's heapq (which you used in D2) operates on a plain list rather than handing you a Heap class — and it's the common point of confusion, so name it plainly: heapq gives you functions over a list, not an object. Insert and pop-min are both O(log n) (they walk one root-to-leaf path restoring the property); peeking the minimum is O(1) because it's always sitting at index 0. Build one by hand once, below, and heapq, heapsort (D6), and Dijkstra (D5) all stop being magic.

pythonclass MinHeap:
    def __init__(self):
        self.a = []
    # index math for the array-as-tree:
    #   parent(i) = (i-1)//2 ; left(i) = 2i+1 ; right(i) = 2i+2

    def push(self, x):
        self.a.append(x)                 # add at the end ...
        self._sift_up(len(self.a) - 1)   # ... then bubble up to restore order

    def pop(self):
        if not self.a:
            raise IndexError("pop from empty heap")
        self.a[0], self.a[-1] = self.a[-1], self.a[0]   # swap min to the end
        smallest = self.a.pop()          # remove it — O(1)
        if self.a:
            self._sift_down(0)           # restore order from the root
        return smallest

    def _sift_up(self, i):
        while i > 0:
            parent = (i - 1) // 2
            if self.a[i] >= self.a[parent]:
                break
            self.a[i], self.a[parent] = self.a[parent], self.a[i]
            i = parent

    def _sift_down(self, i):
        n = len(self.a)
        while True:
            small, l, r = i, 2*i + 1, 2*i + 2
            if l < n and self.a[l] < self.a[small]: small = l
            if r < n and self.a[r] < self.a[small]: small = r
            if small == i:
                break
            self.a[i], self.a[small] = self.a[small], self.a[i]
            i = small

h = MinHeap()
for v in [5, 1, 8, 3]: h.push(v)
print(h.pop(), h.pop())                  # 1 3 — always the smallest next

7 · Trie — the prefix tree advanced

Start typing "car" into any search box and watch what happens. Before you've finished the third letter, it's already offering "cardigan," "car insurance," "cardinal" — instantly, out of a dictionary of millions of phrases, and it doesn't get slower as that dictionary grows. How? It certainly isn't scanning all million entries and checking which start with "car" on every keystroke; that would be O(n) per letter and the box would lag. The structure that makes autocomplete feel instant is the trie, and its trick is to organize words not as a list to filter but as a shared road-map of letters.

A trie (prefix tree — pronounced "try," from retrieval) stores strings by character, one node per character, sharing common prefixes. Lookup and insert are O(L) in the word length L — independent of how many words are stored. Sit with that complexity, because it's the whole reason the structure earns its keep: finding a word costs time proportional to the length of the word, not the size of the dictionary. Ten words or ten million, looking up a five-letter prefix is five steps. Picture a subway map where "car," "card," and "cart" all ride the same c → a → r track and only split at the final stop — the shared prefix is laid down once, and each word is just a path from the central station out to its own platform.

That path-based storage is also where the two classic gotchas live. First: a trie needs a way to mark where a real word ends, separate from merely passing through. Without an end-of-word flag, a trie holding "card" would wrongly claim "car" is a stored word just because the path exists — so you plant a little marker (in the lab, a "$" key) at each true word ending. A node can be both an ending and a through-point: "car" ends at r, yet the path continues to d for "card." Second, the honest trade-off: tries buy their prefix speed with memory. Every character can spawn its own node, so a trie of many short, dissimilar strings can use far more space than just storing the strings in a set — which is exactly why you reach for a trie when prefix queries are the point (autocomplete, spell-check, IP-routing longest-prefix match) and not when you only ever ask "is this exact word present?" (a hash set from D3 is smaller and simpler for that). Use the right tool for the query you actually have.

pythonclass Trie:
    def __init__(self):
        self.root = {}                    # nested dicts: char -> child dict
        self._END = "$"                  # marks a complete word

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {}) # descend, creating as needed
        node[self._END] = True

    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node: return None
            node = node[ch]
        return node

    def starts_with(self, prefix):     # all words with this prefix
        node = self._find(prefix)
        if node is None: return []
        out = []
        def dfs(nd, path):
            for ch, child in nd.items():
                if ch == self._END: out.append(prefix + path)
                else: dfs(child, path + ch)
        dfs(node, "")
        return out

t = Trie()
for w in ["cat", "car", "card", "dog"]: t.insert(w)
print(sorted(t.starts_with("ca")))     # ['car', 'card', 'cat']

8 · Segment & Fenwick trees expert (concept) advanced

Imagine a live leaderboard, or a running "tokens spent in the last hour" meter on an agent dashboard. Two things happen constantly: values change (someone scores, another API call burns tokens) and you're asked about ranges ("total for players 40–60," "sum over this window"). Back in D1 you learned the prefix-sum trick, which answers any range-sum query in a blazing O(1) — but only for data that sits still. The moment a single value updates, the entire prefix array behind it is stale, and rebuilding it is O(n). Do that on every update and your slick O(1) queries are dragging an O(n) anchor. That tension — cheap queries versus cheap updates — is the exact problem this section resolves.

Concretely, D1's prefix-sum answered range queries in O(1) — but only if the data never changes. When values update between queries, rebuilding the prefix array is O(n). Two trees fix this by storing partial answers arranged as a tree rather than one flat running total. The intuition is a cache of pre-computed sums over ranges: instead of "the total up to here," each node holds "the total of this slice." Change one underlying value and you don't rebuild everything — you only refresh the handful of slices that contain it, which (because a balanced tree is only O(log n) tall) is just O(log n) nodes on the path back to the root. Answering a range query likewise stitches together a few cached slices instead of adding up every element. Both operations land at O(log n) — the balanced middle ground between the two lopsided extremes.

A fair word on when this earns its complexity, because it's the rarest structure in the chapter and easy to over-reach for. If your data is static, don't build one — plain prefix-sums are simpler and faster. If you only ever need whole-array totals, a running counter is enough. Segment and Fenwick trees pay off specifically when you have both frequent point-updates and frequent range-queries on the same changing array — live analytics, leaderboards, rolling cost/usage windows, and a great deal of competitive programming. The two differ in reach: a segment tree handles any associative combine (sum, min, max, gcd) and is the general tool, while a Fenwick tree (Binary Indexed Tree) does the sum-style case only, but in strikingly little code and memory via a bit trick. You'll rarely type either from scratch in day-to-day agent code — but knowing they exist is what stops you from writing an accidental O(n) rebuild loop when a changing range keeps getting queried.

• Segment tree: a binary tree where each node stores an aggregate (sum/min/max) over a range. Both point-update and range-query are O(log n). Flexible — any associative operation.
• Fenwick tree (BIT): a compact array cleverly indexed by bit tricks. Also O(log n) update + prefix-query, with tiny memory and code — but sums only.

pythonclass Fenwick:
    def __init__(self, n):
        self.t = [0] * (n + 1)          # 1-indexed
    def update(self, i, delta):        # add delta at position i
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)                # jump by lowest set bit
    def prefix_sum(self, i):           # sum of [0..i]
        i += 1; s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)
        return s

Exercises expert

🎯 Interview practice interview

The interview questions this topic gets asked — worked, with code. For the full pattern catalog see D8 · Big Tech DSA patterns.

pythonfrom collections import deque
def level_order(root):
    out, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft(); level.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        out.append(level)
    return out

pythondef is_valid_bst(root, lo=float("-inf"), hi=float("inf")):
    if not root: return True
    if not (lo < root.val < hi): return False
    return (is_valid_bst(root.left, lo, root.val) and
            is_valid_bst(root.right, root.val, hi))

Checkpoint expert

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val; self.left = left; self.right = right

def max_depth(node):                   # O(n) time, O(h) stack
    if node is None:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(max_depth(root))                 # 3

from collections import deque

class T:
    def __init__(self, v, l=None, r=None): self.v, self.l, self.r = v, l, r

def inorder(n):   return inorder(n.l) + [n.v] + inorder(n.r) if n else []
def preorder(n):  return [n.v] + preorder(n.l) + preorder(n.r) if n else []
def postorder(n): return postorder(n.l) + postorder(n.r) + [n.v] if n else []

def level_order(root):                 # BFS, O(n)
    out, q = [], deque([root] if root else [])
    while q:
        n = q.popleft(); out.append(n.v)
        if n.l: q.append(n.l)
        if n.r: q.append(n.r)
    return out

r = T(4, T(2, T(1), T(3)), T(6, T(5), T(7)))
print(inorder(r))       # [1,2,3,4,5,6,7]  -> sorted, because it's a BST
print(level_order(r))   # [4,2,6,1,3,5,7]

class Node:
    def __init__(self, key): self.key = key; self.left = self.right = None

def insert(root, key):                 # avg O(log n)
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None

root = None
for k in (5, 3, 8, 1, 4): root = insert(root, k)
print(search(root, 4), search(root, 9))   # True False

def is_valid_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if not (low < node.val < high):    # every node must respect ancestor bounds
        return False
    return (is_valid_bst(node.left, low, node.val) and
            is_valid_bst(node.right, node.val, high))

class N:
    def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r

good = N(5, N(3, N(1), N(4)), N(8))
bad  = N(5, N(3, N(1), N(6)), N(8))    # 6 > 5 but sits in the left subtree
print(is_valid_bst(good), is_valid_bst(bad))   # True False

class MinHeap:
    def __init__(self): self.h = []
    def push(self, x):                 # O(log n)
        self.h.append(x); i = len(self.h) - 1
        while i > 0 and self.h[(i - 1) // 2] > self.h[i]:
            p = (i - 1) // 2
            self.h[i], self.h[p] = self.h[p], self.h[i]; i = p
    def pop(self):                     # O(log n)
        h = self.h; h[0], h[-1] = h[-1], h[0]
        top = h.pop(); i, n = 0, len(h)
        while True:
            l, r, s = 2*i+1, 2*i+2, i
            if l < n and h[l] < h[s]: s = l
            if r < n and h[r] < h[s]: s = r
            if s == i: break
            h[i], h[s] = h[s], h[i]; i = s
        return top

heap = MinHeap()
for x in (5, 1, 3, 8, 2): heap.push(x)
print([heap.pop() for _ in range(5)])   # [1, 2, 3, 5, 8]

class Trie:
    def __init__(self): self.root = {}
    def insert(self, word):            # O(L)
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True               # end-of-word marker
    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node: return None
            node = node[ch]
        return node
    def starts_with(self, prefix):     # O(L)
        return self._find(prefix) is not None
    def complete(self, prefix):        # collect words under the prefix
        node = self._find(prefix); out = []
        def dfs(n, path):
            if "$" in n: out.append(prefix + path)
            for ch, child in n.items():
                if ch != "$": dfs(child, path + ch)
        if node: dfs(node, "")
        return sorted(out)

t = Trie()
for w in ("cat", "car", "card", "dog"): t.insert(w)
print(t.starts_with("ca"))   # True
print(t.complete("car"))     # ['car', 'card']

Knowledge check check yourself