Appendix · Data Structures & Algorithms · Part 4

Trees & Heaps

Q: What ordering property defines a binary search tree (BST), and why does it enable O(log n) search on a balanced tree?

In a BST every node's left subtree holds smaller keys and its right subtree holds larger keys. Comparing the target to a node discards one whole subtree each step, halving the search space on a balanced tree for O(log n).

Q: What is a trie (prefix tree) best suited for, and how does it store words?

A trie stores strings by shared prefixes: each edge is a character and a path from the root spells a prefix. It excels at prefix lookups and autocomplete, where cost depends on word length rather than the number of stored words.

Hierarchical structures — where each node points to children, not just a neighbour. Trees give you O(log n) search/insert when kept balanced, ordered traversal for free, and the heap that powers every top-k retrieval. We build binary trees, BSTs, a heap from scratch, and a trie, then touch the advanced range-query trees.

⏱️ ~2.5 hours🎯 Basic → Expert🌳 O(log n)runnable

Learning objectives

Speak the tree vocabulary: root, leaf, height, depth, subtree, balanced.
Traverse a tree four ways (pre/in/post-order DFS and level-order BFS).
Build a binary search tree and explain why balance is everything.
Know what AVL and red-black trees guarantee (and where Python uses them).
Implement a binary heap from scratch — sift-up/sift-down, heapify.
Build a trie for prefix search and understand segment/Fenwick trees at a high level.

1 · Tree terminology basic

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

Why log n keeps appearingA balanced binary tree of height h holds up to 2^(h+1) − 1 nodes. Flip it around: n nodes fit in height ≈ log₂ n. So any operation that walks one root-to-leaf path does O(log n) work. Doubling your data adds just one level. That's the magic of logarithmic structures.

2 · Binary trees basic → intermediate

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.

Example code for learning — review, test, and adapt it before running against real or production systems. Commands can create, change, or delete resources. See the Terms & Disclaimer.

Try it — node type + basic measures

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

▶ How this works

A tree is data shaped like a family tree: one node at the top (the root), and every node can point down to children. A binary tree means each node has at most two children, named left and right. This block defines what one node looks like and then measures the tree.

The TreeNode class holds three things: a value, and two links — left and right — that each point to another TreeNode or to None (meaning "nothing there").
height(node) is recursive — it calls itself on the children. The rule return 1 + max(height(node.left), height(node.right)) reads as: "my height is 1 more than my taller child." The base case if node is None: return -1 makes a lone leaf come out as height 0.
count(node) uses the same recursive shape: 1 (for me) plus the count of everything on my left plus everything on my right.
The last two lines build a tiny tree — a root 4 with children 2 and 6 — and measure it.

What the output means: 1 3 — the tree is 1 level deep below the root (height 1) and holds 3 nodes in total.

Try this: Add grandchildren, e.g. TreeNode(2, TreeNode(1)), and rerun. The height grows to 2 and the count to 4. Notice you never wrote a loop — recursion walks the whole tree for you.

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

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). DFS has three orders depending on when you process the current node relative to its children.

Four ways to visit every node. DFS (pre/in/post) uses a stack; BFS uses a queue. For a BST, in-order yields the values in sorted order.

🗺️ How to read this diagram

"Traversing" a tree means visiting every node once. This picture shows the same little tree (root F) visited four different ways, and the order each way spits out.

Circles are nodes, lines are parent→child links. F is the root at the top; each node sits one level lower than its parent. The bottom row (A, D, I) are leaves — no children.
Pre-order (blue) visits the node first, then its left side, then its right: F B A D G I. Handy for copying a tree top-down.
In-order (green) visits left, then the node, then right: A B D F G I. The green note flags the magic: for a search tree this comes out sorted.
Post-order (amber) visits both children first, then the node: A D B I G F. Good for deleting a tree bottom-up.
Level-order visits row by row, left to right (F B G A D I) — this is breadth-first (BFS), using a queue instead of going deep.

In short: Pre/in/post differ only in when you record the current node — before, between, or after its two children. Level-order is the odd one out: it goes wide, not deep.

Try it — all four traversals

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

▶ How this works

Here are the four traversals as code. The three depth-first ones (pre/in/post) are almost identical — the only difference is the line that records node.value moves to a different spot. Level-order is separate because it uses a queue.

preorder does out.append(node.value) first, then recurses into node.left and node.right. Node before children.
inorder recurses left, then appends the value, then recurses right. Left → node → right. For a BST this yields sorted values.
postorder recurses into both children before appending. Children before node.
level_order is breadth-first: it uses a deque as a queue. q.popleft() takes the oldest waiting node, prints it, then q.append(...) adds its children to the back — so whole levels come out in order.

What the output means: Each function fills the out list in its own order; for the tree 5,3,7,1,4 built later, inorder gives [1,3,4,5,7].

Try this: Take the tree from section 2 (root 4, children 2 and 6) and run each traversal. Pre-order gives [4,2,6], in-order [2,4,6], post-order [2,6,4]. Watch how only the node's position in the output shifts.

The key insight: in-order of a BST is sortedDFS uses a stack (explicit or the call stack); BFS uses a queue. Memorize that pairing. And remember in-order traversal of a binary search tree yields the values in sorted order — that single fact connects trees to sorting (D6) and is a favourite interview question.

4 · Binary search tree (BST) advanced

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.

The BST invariant makes search a series of left/right choices. Each comparison discards a whole subtree, so lookup is O(log n) when balanced. (In-order traversal of this tree gives 1 3 4 5 7 — sorted.)

🗺️ How to read this diagram

A binary search tree (BST) is a binary tree with one rule that makes searching fast. This diagram shows the rule and traces a search for the value 4.

The rule (invariant): for every node, everything in its left subtree is smaller and everything in its right is larger. Here root 5 has smaller 3 on the left and larger 7 on the right, and this holds at every node.
The blue arrows are the search path for 4. At each node you compare and pick one direction — you never look at the other side.
Start at 5: 4 < 5, so go left to 3. Then 4 > 3, so go right to the green 4 — found it, in just two steps.
Because each comparison throws away a whole subtree, search does about log₂ n steps when the tree is balanced — the same halving idea as binary search on a sorted list.

In short: Reading a BST in-order (left, node, right) here gives 1 3 4 5 7 — sorted. That is the same in-order traversal from the previous section, applied to an ordered tree.

Try it — insert & search

Illustrative fragment — defines demo values / files are needed before this runs standalone.

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!

▶ How this works

This builds a BST you can insert into and search. Both operations are just "compare, then go left or right" — the ordering rule guarantees the item can only be in one place.

insert(value) calls the recursive helper _insert. When it reaches a None spot (an empty branch), it returns a fresh TreeNode(value) — that is where the value belongs.
The choice if value < node.value: go left, elif value > node.value: go right, keeps the invariant true. Equal values are ignored (no duplicates).
search(value) loops instead of recursing: at each node, return True on a match, otherwise step to node.left or node.right depending on the comparison. Fall off the bottom → False.
The demo inserts 5, 3, 7, 1, 4 in that order, then runs the inorder traversal on the result.

What the output means: [1, 3, 4, 5, 7] — even though we inserted them jumbled, in-order comes out sorted. That is the BST invariant paying off.

Try this: Insert the values already sorted — 1,2,3,4,5 — and picture the shape: every value is larger, so every node hangs to the right, making a straight line. That slow, lopsided case is exactly what the next section fixes.

The BST's fatal flaw — degenerationInsert already-sorted data (1,2,3,4,5) into a plain BST and every node goes right: you get a linked list of height n, and search degrades to O(n). This is why real systems use self-balancing trees, which rearrange themselves to stay short — next section.

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

A self-balancing BST performs rotations after insert/delete to keep the height at O(log n), guaranteeing fast operations regardless of insertion order.

Why balancing matters. Inserting sorted data into a plain BST degenerates into a O(n) chain. A rotation lifts the middle value to the root, restoring O(log n) height — the core move inside AVL & red-black trees.

🗺️ How to read this diagram

This compares a broken-looking BST (left) with the same values after one rotation (right). It shows why real databases use self-balancing trees.

Left side: inserting 1, 2, 3 already in order makes each node hang off the one before it — a straight downward chain (drawn in red). This is a "degenerate" tree; it is really a linked list of height n, so search is slow (O(n)).
The vertical dashed line just separates the before and after pictures.
Right side: a rotation lifts the middle value 2 up to become the root, with 1 and 3 as its two children. Now the tree is short and bushy (drawn green).
Height dropped from n to about log n, so search is fast again (O(log n)). The blue arrows show the new parent→child links after the move.

In short: A rotation is a local rearrangement that keeps the left < node < right rule but shortens the tree. AVL and red-black trees do these rotations automatically after every insert so the tree never degenerates.

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

The one rotation everything is built from

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

▶ How this works

This is the single move that all self-balancing trees are built from: a right rotation. The ASCII diagram in the comments shows a left-heavy node y being rebalanced so its child x becomes the new top.

Before: y is on top with left child x; x has subtrees A and B, and y has right subtree C. We want x on top.
x = y.left grabs the child that will become the new root.
y.left = x.right — x's right subtree B is in the way (it sits between x and y in value), so it moves to become y's new left child.
x.right = y hangs the old root y under x. return x hands back the new subtree root so the caller can reattach it.

What the output means: No printout — this is a building block. It returns the rebalanced subtree with x on top, still obeying left < node < right.

Try this: Trace it on the degenerate tree from the diagram: y=2, x=1 would not help (1 has no children), but rotating around the chain repeatedly is how the middle value bubbles up to the top.

What you actually use in PythonPython has no built-in balanced-tree type. When you need sorted, ordered operations, you either (a) keep a list sorted with the bisect module (D6) for O(log n) search + O(n) insert, or (b) use the third-party sortedcontainers library (SortedList, SortedDict) which gives O(log n) everything via B-tree-like blocks. Knowing the guarantees lets you pick correctly.

6 · Binary heap — from scratch advanced

A binary heap is a complete binary tree with the heap property: every parent ≤ its children (a min-heap). Because it's complete, it's stored in a flat array — no node objects — with arithmetic child/parent indices. That's why heapq (D2) operates on a plain list. Insert and pop-min are both O(log n); peeking the min is O(1).

A heap is a tree living in an array. Because the tree is complete, children/parent are pure index arithmetic — so heapq needs only a plain list. The min is always at index 0 (O(1)); push/pop restore order in O(log n).

🗺️ How to read this diagram

A heap is a tree that is deliberately kept as short and full as possible, and it is cleverly stored inside a plain list — no node objects at all. This diagram shows both views side by side.

Left (tree view): a min-heap. The only rule is every parent is ≤ its children. So the smallest value, 1, is always at the very top. Note it is not fully sorted — 5 sits above 4 — only the parent-below-child rule matters.
Right (array view): the same values laid out in a flat list, reading the tree top-to-bottom, left-to-right: [1, 3, 5, 8, 4]. The small numbers 0..4 beneath are the list indexes.
The index math links the two views without any pointers: a node at index i has children at 2i+1 and 2i+2, and its parent is at (i−1)//2. That is why heapq works on an ordinary list.
The min is always at index 0, so peeking the smallest is instant (O(1)); adding or removing then re-sorts along one path (O(log n)).

In short: Check the math: index 0 holds 1; its children are at indexes 1 and 2 (values 3 and 5) — both ≥ 1. The rule holds everywhere.

Try it — implement the min-heap yourself

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

▶ How this works

This implements a min-heap from scratch, storing everything in one list self.a. Adding and removing both work by putting the item in the easy spot, then letting it "bubble" to where the parent-≤-children rule holds again.

push(x): append x to the end of the list, then _sift_up — repeatedly swap it with its parent while it is smaller. It climbs until its parent is no bigger, restoring the heap rule.
pop(): the min lives at index 0. We swap it with the last item, pop() the last item off (now the old min — cheap to remove from the end), then _sift_down(0) to push the swapped-in value back down.
_sift_down looks at a node and its two children (indexes 2*i+1 and 2*i+2), finds the smallest of the three, and swaps down toward it — repeating until the node is already smallest, i.e. the rule holds.
The demo pushes 5, 1, 8, 3 and pops twice.

What the output means: 1 3 — pop always returns the current smallest. Pop again and you'd get 5, then 8: a heap hands out items in sorted order one at a time.

Try this: This is exactly how heapq and top-k retrieval work under the hood. Change the pushed values and predict the first two pops before running — it is always the two smallest.

🔗 Used in the courseThis is the engine under heapq.nlargest(k, scored_chunks) — RAG top-k retrieval (Ch 3). Heaps also power Dijkstra's shortest-path (D5) and heapsort (D6). Building it once demystifies all three.

7 · Trie — the prefix tree advanced

A trie (prefix tree) 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. It's the structure behind autocomplete, spell-check, and IP routing tables.

A trie shares prefixes. "cat", "car", "card" all reuse the c→a path; only the diverging suffix costs extra nodes. Lookup walks one character at a time — O(L), regardless of how many words are stored.

🗺️ How to read this diagram

A trie (say "try", a prefix tree) stores words letter by letter. Words that begin the same share the same path, so common prefixes are stored only once. This diagram stores cat, car, card, dog.

Each node is one character; each downward edge adds a letter. Start at root and read down a path to spell a word.
Sharing: cat, car, and card all begin c → a, so that path exists once. They only split where they differ: into t, r, and (past r) d.
Green nodes mark the end of a real word (see the legend). A node can be green and still continue — car ends at r, but card keeps going to d.
dog shares nothing with the c-words, so it gets its own branch from the root.

In short: To find every word starting with ca, walk root→c→a once, then collect all green endings below. Lookup cost depends on the word length, not on how many words are stored — that is why tries power autocomplete.

Try it — autocomplete

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']

▶ How this works

This builds the trie from the diagram using nothing but nested dictionaries. Each dict maps a character to the next dict down; a special key marks where a word ends.

self.root = {} is an empty dictionary. self._END = "$" is a sentinel key that means "a word ends here" ($ is safe because words are letters).
insert(word) walks the characters, and node = node.setdefault(ch, {}) either follows an existing child dict or creates an empty one — this is how shared prefixes get reused. At the end it sets node[self._END] = True.
_find(prefix) walks the same way but returns None the moment a character is missing — that means the prefix is not present.
starts_with(prefix) finds the prefix node, then a small recursive dfs explores every dict below it, rebuilding words and collecting each one that hits the $ end-marker.

What the output means: ['car', 'card', 'cat'] — every stored word beginning with "ca", gathered by walking down from the shared c→a node.

Try this: Add t.insert("care") and search "car" again — you'll get care too, sharing the c-a-r path and only adding one node for e.

🔗 Used in the courseCommand/tool-name autocomplete, fast prefix filtering of a large runbook index, and tokenizer vocabularies all lean on tries or trie-like structures — you'll see the tokenization angle in the advanced string track.

8 · Segment & Fenwick trees expert (concept) advanced

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:

A segment tree keeps range answers and allows updates. Each node caches an aggregate over a range; changing one leaf only touches its log n ancestors — so both point-update and range-query are O(log n) (a Fenwick tree does the sum-only case more compactly).

🗺️ How to read this diagram

A plain prefix-sum answers "sum of a range" instantly, but breaks when values change. A segment tree fixes that: each node stores the sum of a slice of the array, so both updating a value and querying a range stay fast.

The leaves (bottom row) are the actual array values 3, 1, 4, 3. Each parent stores the sum of its children's range — e.g. [0..1]=4 is 3+1.
The root [0..3]=11 is the total of the whole array. Ranges get smaller as you go down, down to a single cell at each leaf.
Updating one value (a leaf, shown by the blue arrow) only requires fixing the sums on the path back up to the root — that is just log n nodes, not the whole array.
Querying a range combines a handful of these cached node-sums instead of adding every element, so both update and query are O(log n).

In short: Think of it as a cache of partial sums arranged as a tree. Change one leaf, refresh its few ancestors, done. A Fenwick tree (next code block) does the sum-only version even more compactly.

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.

Fenwick tree — 12 lines for O(log n) updatable prefix sums

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

▶ How this works

A Fenwick tree (a.k.a. Binary Indexed Tree) is the compact cousin of the segment tree for sums. In ~12 lines it supports updating a value and asking for a prefix sum, both in O(log n), using a bit trick to hop between responsible slots.

self.t = [0] * (n + 1) is a 1-indexed array of running partial sums (index 0 is unused).
update(i, delta) adds delta at position i, then climbs to every slot that includes i in its range. The magic step i += i & (-i) jumps forward by the lowest set bit — that is the compact trick that lands exactly on the right slots.
prefix_sum(i) adds up the slots covering [0..i], walking down with i -= i & (-i), the mirror of the update jump.
Both loops run about log n times because each step clears or adds one bit.

What the output means: No demo call here, but after e.g. update(0,3); update(1,1), prefix_sum(1) returns 4 — the running total of positions 0 and 1.

Try this: You don't need to memorize the bit trick to use it — just know a Fenwick tree gives updatable prefix sums in O(log n) with tiny code, ideal for rolling counters and leaderboards.

When you'd reach for theseLive analytics dashboards, leaderboards, and "sum/max of a moving range that keeps changing" — e.g. rolling token-usage or cost windows in an agent monitoring system. Rare in day-to-day agent code, essential in competitive programming and high-frequency analytics.

Exercises expert

Practice

Write an iterative in-order traversal using an explicit stack (no recursion).
Check whether a binary tree is a valid BST (hint: track a min/max range as you recurse).
Find the lowest common ancestor of two nodes in a BST.
Turn your MinHeap into a MaxHeap without changing the logic (hint: negate, or a custom comparator).
Add a delete(word) to the trie that also prunes now-empty branches.

🎯 Interview practice interview

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

Level-order traversal (classic) — BFS

A queue processes the tree ring by ring; capture one list per level.

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

▶ How this works

This is the classic interview version of level-order traversal: return one list per level instead of one flat list. The trick is to measure how many nodes are on the current level before you start adding the next level's nodes.

q is a queue (a deque) seeded with the root. The outer while q: runs once per level.
for _ in range(len(q)): is the key line — len(q) at this moment is exactly the count of nodes on the current level, so this inner loop drains precisely one level.
For each node we popleft() it, record its value into level, and append its children to the back of the queue for the next round.
After the inner loop, level is a full row; append it to out.

What the output means: A list of lists, one per depth — e.g. [[F], [B, G], [A, D, I]] for the tree in the traversal diagram.

Try this: The single idea worth remembering: snapshot len(q) before draining, so each pass handles exactly one level. That is what turns a flat BFS into a per-level one.

Validate a BST (classic)

Recurse with an allowed (low, high) range; each node must fall strictly inside it.

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

▶ How this works

This checks whether a binary tree is a valid BST. The naive "left child < me < right child" check is not enough — a deep descendant could still violate the order. The fix is to carry an allowed (low, high) range down the recursion.

Every node must satisfy lo < root.val < hi. The root starts with an open range from -inf to +inf.
Going left, values must stay below the current node, so the high bound tightens to root.val: is_valid_bst(root.left, lo, root.val).
Going right, values must stay above the current node, so the low bound tightens to root.val: is_valid_bst(root.right, root.val, hi).
An empty spot (not root) is trivially valid — return True. Both sides must pass (and).

What the output means: True for a proper BST, False the moment any node escapes its inherited (low, high) window.

Try this: Picture a tree where a left-subtree grandchild is bigger than the root: the range passed down would forbid it, so this catches the bug the simple parent-only check misses.

Checkpoint expert

Traverse a tree with all four orders and know which uses a stack vs a queue.
Explain the BST invariant, why in-order is sorted, and how it degenerates.
State what AVL/red-black trees guarantee and what Python offers instead.
Implement a heap with sift-up/down and connect it to heapq and top-k retrieval.

🪜 Practice ladder beginner → industry

Six graded exercises, easy to real-world. Try each before opening its solution.

Exercise 1 · Build a tree and count depthBeginner

Context: Recursion on trees mirrors their recursive shape; computing height is the gentlest introduction to that pattern.

Your task: Define a binary-tree node, build a small tree, and compute its maximum depth (height) recursively in O(n).

Requirements:

A node holds a value plus left/right child references
Height is 1 + max(left height, right height)
An empty subtree contributes height 0
O(n), visiting each node once

💡 Hint: The recursive definition is the whole solution: the base case is the empty child, and the depth of a leaf is 1.

Show solution

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

Depth = 1 + the deeper child's depth; the base case (empty = 0) stops the recursion.

Exercise 2 · The four traversalsIntermediate

Context: The four traversals are the tree programmer's alphabet, and in-order over a BST has a special property worth remembering.

Your task: Perform in-order, pre-order, and post-order DFS plus a BFS level-order walk on a binary tree, and note what in-order yields on a BST.

Requirements:

In-order = left, node, right
Pre-order = node, left, right; post-order = left, right, node
Level-order uses a queue and visits depth by depth
State that in-order traversal of a BST emits values in sorted order

💡 Hint: The three DFS orders differ only in when you visit the node relative to its children; BFS needs a queue rather than the call stack.

Show solution

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]

In-order on a BST yields sorted keys — the property behind BST range queries.

Exercise 3 · BST insert & searchAdvanced

Context: BST insert and search are the operations that make a tree a searchable index — and they expose why balance matters.

Your task: Implement insert and search for a binary search tree, and state why the cost is average O(log n) but worst O(n).

Requirements:

Insert places a value left if smaller, right if larger, walking down from the root
Search follows the same comparisons to find or miss a value
Average depth is O(log n) on balanced data
State that sorted inserts degenerate the tree into a chain → O(n)

💡 Hint: Both operations are the same downward walk; feeding already-sorted values in order is what collapses the tree to a linked list.

Show solution

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

Each comparison discards half the remaining keys — O(log n) if balanced. Inserting sorted data makes a linked-list-shaped tree (O(n)), which is why balanced trees (AVL/red-black) exist.

Exercise 4 · Validate a BSTExpert

Context: Validating a BST (classic) has a famous trap: checking only immediate children passes trees that are actually invalid.

Your task: Given a binary tree, decide whether it is a valid BST by passing down min/max bounds, in O(n).

Requirements:

Every node must lie strictly within an inherited (low, high) range
Descending left tightens the upper bound; descending right tightens the lower
Explicitly reject the local-comparison-only approach as insufficient
O(n), visiting each node once

💡 Hint: A node isn't just greater than its parent — it must respect every ancestor's bound, which you carry down as a shrinking interval.

Show solution

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

The bound narrows as you descend: a left child must be below its parent and every ancestor it turned left from.

Exercise 5 · A min-heap from scratchProfessional

Context: A hand-built binary min-heap is exactly what heapq does under the hood, and the array-index arithmetic is the point of the exercise.

Your task: Implement an array-backed binary min-heap with push and pop using sift-up and sift-down, both O(log n).

Requirements:

Store the heap as a flat array with the standard parent/child index formulas
push appends then sifts up to restore the invariant
pop removes the root, moves the last element up, then sifts down
Both operations are O(log n)
The root is always the minimum

💡 Hint: For index i, children live at 2i+1 and 2i+2 and the parent at (i−1)//2; sifting just swaps toward the correct level.

Show solution

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]

The array encodes the tree: children of i are 2i+1/2i+2. Sifting touches one root-to-leaf path, hence O(log n).

Exercise 6 · Trie for autocompleteIndustry scenario

Context: A trie powers prefix autocomplete with lookups that don't slow down as the dictionary grows — a structure interviewers love for search features.

Your task: Build a prefix tree (trie) supporting insert and starts_with to drive autocomplete, with lookup O(L) in the query length.

Requirements:

Each node maps a character to a child node
insert walks/creates a path of characters and marks word ends
starts_with succeeds if the prefix path exists
Lookup cost is O(L) in the prefix length, independent of dictionary size
Distinguish a stored word from a mere prefix

💡 Hint: Descend one node per character; starts_with only needs the path to exist, while a full-word lookup also checks the end-of-word flag.

Show solution

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']

Shared prefixes are stored once, so query cost depends on the word length, not the dictionary — how search boxes stay instant.

Knowledge check check yourself

✓ Knowledge check

What ordering property defines a binary search tree (BST), and why does it enable O(log n) search on a balanced tree?

Show answer

In a BST every node's left subtree holds smaller keys and its right subtree holds larger keys. Comparing the target to a node discards one whole subtree each step, halving the search space on a balanced tree for O(log n).

✓ Knowledge check

What is a trie (prefix tree) best suited for, and how does it store words?

Show answer

A trie stores strings by shared prefixes: each edge is a character and a path from the root spells a prefix. It excels at prefix lookups and autocomplete, where cost depends on word length rather than the number of stored words.

Educational content, provided as-is and without warranty. Code samples are examples — review, test, and adapt them before using in production. See the Terms of Use & Disclaimer. Use at your own risk.

Learning objectives

1 · Tree terminology basic

2 · Binary trees basic → intermediate

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

4 · Binary search tree (BST) advanced

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

6 · Binary heap — from scratch advanced

7 · Trie — the prefix tree advanced

8 · Segment & Fenwick trees expert (concept) advanced

Exercises expert

🎯 Interview practice interview

Checkpoint expert

🪜 Practice ladder beginner → industry

Knowledge check check yourself

More in Data structures & algorithms