Trees & Heaps -- Inventing Fast Lookup

A tree is nodes connected downward: each node holds a value and has up to two children, left and right.

Here is the arithmetic expression 2 * 3 + 4 drawn as a tree:

        +
       / \
      *   4
     / \
    2   3

Leaves are numbers; internal nodes are operators. This is exactly how compilers see your code (Python, SQL, C++ -- everything is parsed into trees).

The Node class and a tree printer are provided -- run this cell as-is.

Write evaluate(node) that computes the value of an expression tree.

Before you code:

• If the node's value is a number (leaf) -- what is the answer?
• If it is "+" -- what two smaller problems must you solve first? (This is recursion on a tree: each child is a smaller tree.)

Support +, -, *, /.

evaluate(expr)   # 10   (2*3 + 4)

Build the tree for (2 + 3) * (10 - 4) using Node, print it with print_tree, and check that evaluate returns 30.

Notice: the tree needs no parentheses. The structure is the precedence.

Back to our fast-lookup problem. Here is the one rule that makes a tree searchable:

BST rule: everything in a node's left subtree is smaller than the node's value; everything in the right subtree is larger.

Play with the animation before coding: BST Visualization. Insert 10, 12, 1, 11, 13, 3 and watch where each lands.

Write insert(node, val) that inserts val into the tree rooted at node and returns the root of the resulting tree.

Think recursively:

• If node is None -- where does the new value go?
• If val < node.val -- which subtree does it belong to? Insert it there and reattach: node.left = insert(node.left, val).

root = None
for v in [10, 12, 1, 11, 13, 3]:
    root = insert(root, v)
print_tree(root)

Compare the printed tree with what the animation showed you.

Write contains(node, val) that returns True if val is in the tree.

The payoff: at each node you compare once and discard half the tree -- the same halving you invented in the Binary Search chapter. That is why find is O(log n)... if the tree is balanced (more on that soon).

contains(root, 11)   # True
contains(root, 7)    # False

Write in_order(node) that returns a list of all values using this recipe: first everything in the left subtree, then the node itself, then the right subtree.

in_order(root)   # ?

Run it. Look carefully at the output. What did you just get for free? (You have invented tree sort: insert n values, walk once, sorted output.)

Where does the smallest value in a BST live? Trace it on the picture.

Write find_min(node) that returns the smallest value in a non-empty tree. No comparisons needed -- just walking.

find_min(root)   # 1

Mirror image: write find_max(node) returning the largest value. Same rule -- no comparisons, just walk. Both of these run in O(height): on a balanced tree of a million values, about 20 steps to either extreme.

Deletion is the tricky one.

Write delete(node, val) that removes val and returns the root of the resulting subtree. Think about what happens in each case:

• What if the node you want to delete has no children?
• What if it has one child?
• What if it has two children -- this is the tricky one. If removing it leaves a "hole", what value could you put there that would keep the BST property? (Hint: you just wrote find_min.)

root = delete(root, 1)     # leaf
root = delete(root, 12)    # two children
in_order(root)             # [3, 10, 11, 13]

Insert 1, 2, 3, 4, 5, 6, 7 in that order and print the tree. What shape do you get?

Every insert went right: the "tree" is a chain -- a glorified linked list, and find is back to O(n). Sorted input is the worst input for a plain BST.

Self-balancing trees (AVL, Red-Black) fix this by rotating nodes on insert to keep the height at log n. Watch one rebalance itself: Red-Black Tree Visualization -- insert 1...10 in order and watch it stay shallow. (Databases use B-Trees -- the same idea, made disk-friendly.)

You insert the numbers 1, 2, 3, 4, 5 (in that order) into an empty BST. What does the tree look like, and how many comparisons does finding the value 5 require?

A. A balanced tree with 3 levels -- finding 5 takes 3 comparisons

B. A straight chain leaning right (like a linked list) -- finding 5 takes 5 comparisons

C. A straight chain leaning left -- finding 5 takes 1 comparison

D. The BST refuses to insert sorted data

You are building a task scheduler (like Unix cron). Tasks arrive at any time:

• task1: run at 1:00pm
• task2: run at 12:30pm
• task3: run at 2:00pm

The scheduler repeatedly needs just one thing: the earliest task. So the operations are: add(task), pop_earliest(). Nothing else. No search, no arbitrary delete.

Before reading on, rate each strategy (fill the ?s in your head):

The BST wins -- but it maintains total order, and we only ever ask for the min. Can a structure that promises less do the job with less work? It exists: the min-heap.

The Heap Shape

A min-heap is a binary tree with one weak promise:

Heap rule: every node is <= its children. (Nothing about left vs right!)

So the minimum is always... where?

Because the shape is always a "filled top-down, left-to-right" tree, we don't need Node objects at all -- we can store it in a plain list:

        1
      /   \
     3     2          stored as:  [1, 3, 2, 8, 5]
    / \
   8   5

For the node at list index i, figure out (try it on the picture above):

• parent(i) = ?
• left_child(i) = ?
• right_child(i) = ?

Write the three functions.

parent(3)       # 1   (8's parent is 3)
left_child(1)   # 3
right_child(0)  # 2

To add a value, append it at the end of the list (this keeps the shape correct). But the heap rule might now be broken -- the new value could be smaller than its parent. How would you fix this?

Write heap_push(heap, val) (in place).

h = [1, 3, 2, 8, 5]
heap_push(h, 0)
h   # [0, 3, 1, 8, 5, 2]  -- 0 climbed to the top

How many swaps can a push cost at most, for a heap of n items? (The tree has $\log_2(n)$ levels -- that is the whole point.)

The minimum is heap[0]. Removing it leaves a hole at the root. To keep the shape, move the last element into the root position. But now the heap rule might be broken -- how would you fix it?

Write heap_pop(heap) that removes and returns the minimum. In place.

Edge case to think about: why must you swap with the smaller child? What if a node has only a left child?

h = [1, 3, 2, 8, 5]
heap_pop(h)   # 1
heap_pop(h)   # 2
heap_pop(h)   # 3

Your heap works on anything comparable -- including tuples, which Python compares by first element. So a task is just (time, name).

Write run_scheduler(tasks) that takes a list of (time, name) tuples, pushes them all into a heap, then pops until empty, returning the task names in execution order.

run_scheduler([(1300, "task1"), (1230, "task2"), (1400, "task3"), (1100, "task4")])
# ["task4", "task2", "task1", "task3"]

1. You already proved it in the stress test: push n values, pop n values -> sorted. Package it as heap_sort(lst) returning a new sorted list. Each of the 2n operations costs O(log n) -- so heap sort is O(n log n), in place-able, no merging needed.
2. Python ships your invention as the heapq module: heapq.heappush, heapq.heappop, and heapq.heapify (which builds a heap from a list in O(n)). Verify your heap agrees with it.

heap_sort([5, 2, 9, 1])   # [1, 2, 5, 9]

In a min-heap, which of the following is guaranteed?

A. The left child is always smaller than the right child

B. Every parent is smaller than or equal to both its children, and the root is the overall minimum

C. The tree is sorted from left to right at every level

D. The smallest element is always at the bottom-left

Both a BST and a min-heap store elements. When would you choose a heap over a BST?

A. When you need to search for arbitrary elements quickly

B. When you repeatedly need the minimum (or maximum) element and don't need to search for arbitrary values

C. When you need to iterate elements in sorted order

D. When the data contains duplicates

Your in_order from Exercise 2.3 relies on Python's call stack. But recursion is not magic -- it's just a stack that Python manages for you. Prove it.

Write in_order_iter(node) that returns the same list as in_order, using no recursion -- manage a plain list as your own stack:

1. From the current node, push nodes while walking left as far as you can.
2. Pop a node -- that's the next value in order.
3. Move to the popped node's right child and repeat, until both the stack and the current node are exhausted.

In Part 1 you evaluated expression trees that were built by hand. Real programs receive expressions as strings: "((3+4)*(9-10))". Turning the string into a tree is called parsing -- it's the front half of every compiler (your evaluate from Exercise 1.1 is the back half).

Write parse(s) for fully parenthesized expressions with the operators +, -, * and non-negative integer numbers (no spaces):

• If the current character is a digit, read the whole number -- that's a leaf Node.
• If it is '(': parse the left sub-expression, read the operator, parse the right sub-expression, expect ')' -- that's an operator Node.

A recursive helper that takes the current position i and returns (node, next_position) works beautifully.

What you just invented -- the trade-off ladder you climbed:

• A dictionary promises the most (any-key O(1)) and pays in memory and lost ordering.
• A BST promises total order and pays log n per operation -- plus a balance headache (solved by AVL / Red-Black trees; B-Trees take the same idea to disk in every database).
• A heap promises the least -- just the minimum -- and is the simplest and fastest of all.

Choosing a data structure = paying only for the promises you actually use.

Bonus tricks: in_order_iter showed that recursion is just a stack you can manage yourself, and parse turned a string into an expression tree -- text in, evaluate-ready tree out.