Phase 4: Non-Linear Data Structures

Everything you have built so far has been a line: lists, strings, stacks, queues and linked lists all have a first element, a last element, and one way to walk from one to the other. This phase is about structures that branch. A binary tree splits into two subtrees at every node, a binary search tree keeps those subtrees ordered so you can find things fast, a heap keeps the smallest element ready at the top, and a trie stores words letter by letter along shared branches.

The thread that ties all of them together is recursion. A tree is defined in terms of smaller trees, so the natural way to process one is with a function that calls itself on each subtree. By the end of this phase you will be able to:

• write a recursive function by naming its base case and its recursive step, and know when memoization is needed;
• traverse a binary tree depth-first (recursively and with an explicit stack) and breadth-first (with a queue);
• use the binary search tree invariant to validate, search and select elements;
• solve "top k" and "k-way merge" problems with heapq;
• build a trie out of nested dictionaries.

Recursion

A recursive function solves a problem by solving a smaller instance of the same problem and doing one extra step. Every recursive function has two parts:

1. a base case: an input so small the answer is known without any further calls;
2. a recursive case: do a little work, then call yourself on something strictly closer to the base case.

def sum_of_digits(n):
    if n < 10:                 # base case: a single digit
        return n
    return n % 10 + sum_of_digits(n // 10)   # one digit + the rest

print(sum_of_digits(1234))

10

It helps to trace the calls by hand. sum_of_digits(1234) cannot answer until sum_of_digits(123) returns, which waits on sum_of_digits(12), which waits on sum_of_digits(1). That last call hits the base case and returns 1; then the waiting calls finish in reverse order: 2 + 1 = 3, 3 + 3 = 6, 4 + 6 = 10.

The call stack

Each unfinished call lives in a frame on the call stack. Python limits how deep that stack can grow; on this site the limit is 6000 frames. Recursing once per element of a large input therefore crashes:

def count_down(n):
    if n == 0:
        return 0
    return 1 + count_down(n - 1)

print(count_down(1000))
print(count_down(100000))

1000
RecursionError: maximum recursion depth exceeded

Two lessons follow. First, if the recursion depth is proportional to the input size, prefer a loop or an explicit stack for large inputs. Second, when you can shrink the problem by half instead of by one, do it: the depth becomes O(log n). Fast exponentiation is the classic example. Since x**8 == (x**4)**2, you can compute power(x, n // 2) once, square it, and multiply by one more x when n is odd. That turns a million multiplications into about twenty.

Memoization

Some recursions are shallow but branch into a huge number of calls, most of which repeat work. The naive Fibonacci definition is the textbook case:

calls = 0

def slow_fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return slow_fib(n - 1) + slow_fib(n - 2)

print(slow_fib(20), calls)

6765 21891

Twenty-two thousand calls to produce a four-digit number, because slow_fib(18) is computed twice, slow_fib(17) three times, and so on down the tree. The fix is memoization: store every result the first time you compute it and look it up afterwards. A dictionary keyed by the argument is all you need, and functools.lru_cache will wrap it for you:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(60))

1548008755920

With the cache, fib(60) makes about 120 calls instead of a few trillion. Memoization is the doorway to dynamic programming, which you will meet in Phase 5.

Common mistakes

• Forgetting the base case, or writing one that is never reached (for example recursing on n - 1 but checking n == 0 when n starts negative).
• Forgetting to return the result of the recursive call. sum_of_digits(n // 10) on its own line computes the value and throws it away.
• Using a mutable default argument such as memo={} and being surprised that it persists between calls. Here that persistence is exactly what you want, but know that it happens.

Practice: Sum of Digits (Recursive), Power with Fast Exponentiation, Fibonacci with Memoization

Binary trees

A binary tree is either empty (None) or a node with a value and two subtrees, left and right, each of which is itself a binary tree. Some vocabulary:

• the root is the topmost node; a leaf has no children;
• a node's children are its left and right; it is their parent; the subtree rooted at a node is that node plus everything below it;
• the depth of a node is the number of edges from the root to it; the height of a tree is the number of nodes (or edges, depending on the problem) on the longest root-to-leaf path.

On this site trees are made of TreeNode objects, which are always available:

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

The level-order list format

Writing out nested TreeNode(...) calls is tedious, so tests describe trees as a level-order list, a common convention on judge sites. Read the list top to bottom, left to right, one level at a time; None marks a missing child, and trailing Nones are dropped.

    3
   / \
  9  20
    /  \
   15   7

root = build_tree([3, 9, 20, None, None, 15, 7])
print(root.val, root.left.val, root.right.left.val)
print(tree_to_list(root))

3 9 15
[3, 9, 20, None, None, 15, 7]

The two Nones say that node 9 has no children, so the next values 15 and 7 belong to 20. Problems that return a tree wrap your result in tree_to_list(...) so the grader can compare plain lists.

Depth-first traversal

Because a tree is defined recursively, most tree functions have the same shape: handle None, then do something with the node and the results from left and right. What differs is the order in which you visit the node relative to its subtrees:

• pre-order: node, left, right (good for copying or printing a tree);
• in-order: left, node, right (for a BST this gives sorted order);
• post-order: left, right, node (good when the node's answer depends on its children, like height).

def preorder(node, out):
    if node is None:
        return
    out.append(node.val)
    preorder(node.left, out)
    preorder(node.right, out)

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)

def postorder(node, out):
    if node is None:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)

root = build_tree([1, 2, 3, 4, 5])
for f in (preorder, inorder, postorder):
    out = []
    f(root, out)
    print(f.__name__, out)

preorder [1, 2, 4, 5, 3]
inorder [4, 2, 5, 1, 3]
postorder [4, 5, 2, 3, 1]

Notice how the traversals pass an accumulator list down; the alternative is to return lists and concatenate them, which is shorter but copies more.

Here is a typical recursive tree function, comparing two trees for equality. Both the None handling and the "combine the two subtree answers" step are in it:

def same_tree(a, b):
    if a is None or b is None:
        return a is b            # both None -> True, one None -> False
    return (a.val == b.val
            and same_tree(a.left, b.left)
            and same_tree(a.right, b.right))

print(same_tree(build_tree([1, 2, 3]), build_tree([1, 2, 3])))
print(same_tree(build_tree([1, 2]), build_tree([1, None, 2])))

True
False

Some problems want a function to return one thing (say, the height of a subtree) while tracking another (the best path seen so far). The usual pattern is a nested helper plus a nonlocal variable, or an attribute on self if you are inside a class. Diameter of a binary tree and "maximum path sum" are both this shape.

Iterative DFS with a stack

Recursion uses the call stack; you can replace it with your own stack to avoid depth limits or to pause and resume a traversal. Pre-order is the easiest: push the right child before the left so the left is popped first.

def preorder_iter(root):
    out = []
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out

print(preorder_iter(build_tree([1, 2, 3, 4, 5])))

[1, 2, 4, 5, 3]

Iterative in-order needs a little more care: walk as far left as you can, pushing nodes; pop one, visit it, then step to its right child and repeat.

def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                 # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()          # the leftmost unvisited node
        out.append(node.val)
        node = node.right
    return out

print(inorder_iter(build_tree([1, 2, 3, 4, 5])))

[4, 2, 5, 1, 3]

Being able to stop this loop early is what makes it useful: if you only need the k-th value, you can return the moment you have counted k pops.

Breadth-first traversal with a deque

DFS dives down one branch before looking at the next. Breadth-first search (BFS) visits all nodes at depth 0, then depth 1, and so on. It needs a queue, and collections.deque gives O(1) popleft:

from collections import deque

def bfs(root):
    out = []
    queue = deque([root]) if root else deque()
    while queue:
        node = queue.popleft()
        out.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return out

print(bfs(build_tree([1, 2, 3, 4, 5])))

[1, 2, 3, 4, 5]

The output is simply the level-order list without the Nones. To group values by level, note that at the start of each round len(queue) is exactly the number of nodes on the current level: pop that many, collect them into one inner list, and everything you pushed in the meantime is the next level. BFS is also the right tool for "minimum depth" and "rightmost node on each level" questions, because it reaches shallow nodes before deep ones.

Common mistakes

• Forgetting that None is a valid tree. Almost every helper needs if node is None: as its first line.
• Treating None as a leaf. A leaf is a node with left is None and right is None; the None you reach below a leaf is not itself a leaf, which matters for path-sum problems.
• Returning None from a function that should return the modified root. In-place transforms like inverting a tree must still return root.
• Using list.pop(0) as a queue. It is O(n); use deque.popleft().

Practice: Maximum Depth of Binary Tree, Invert Binary Tree, Path Sum, Binary Tree Level Order Traversal, Diameter of Binary Tree, Lowest Common Ancestor

Binary search trees

A binary search tree (BST) is a binary tree with an ordering invariant: for every node, every value in its left subtree is smaller than the node's value, and every value in its right subtree is larger. The word every is what people get wrong. It is not enough for the immediate children to be on the correct side; a grandchild in the right subtree must still be larger than the grandparent.

    5
   / \
  4   6
     / \
    3   7      <- 3 is in 5's right subtree but 3 < 5: NOT a BST

The invariant buys you fast search. At each node you compare the target with the node's value and go left or right, discarding half the tree if it is balanced:

def search_bst(node, target):
    while node is not None and node.val != target:
        node = node.left if target < node.val else node.right
    return node

def insert_bst(node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        node.left = insert_bst(node.left, val)
    else:
        node.right = insert_bst(node.right, val)
    return node

root = None
for v in [5, 3, 8, 1, 4]:
    root = insert_bst(root, v)
print(tree_to_list(root))
print(search_bst(root, 4).val)
print(search_bst(root, 7))

[5, 3, 8, 1, 4]
4
None

Insertion follows the same path a search would take and hangs the new node where the search fell off the tree. Note the recursive insert returns the (possibly new) subtree root and the caller stores it: node.left = insert_bst(node.left, val). That pattern of "return the new subtree" shows up in deletion and in tree-building problems too.

In-order gives sorted order

Because the left subtree is smaller and the right subtree is larger, an in-order traversal of a BST visits values in ascending order:

print(inorder_iter(root))

[1, 3, 4, 5, 8]

This single fact solves a family of problems. The k-th smallest value is the k-th node visited in-order. The tree is a valid BST if and only if the in-order sequence is strictly increasing. The in-order successor of a node is the next value in that sequence. Whenever a BST problem seems hard, ask what the in-order traversal looks like.

The other standard technique is to pass bounds down the tree: every value in the subtree under node.left must be less than node.val, and everything under node.right must be greater. A helper valid(node, low, high) that tightens one bound on each step visits every node once and never needs to build a list.

Common mistakes

• Validating only node.left.val < node.val < node.right.val. The tree above passes that check and is still wrong.
• Using <= when the problem forbids duplicates (or vice versa). Read the constraints.
• Initialising the bounds with 0 or -1 instead of float('-inf') and float('inf'); node values can be negative.

Practice: Validate Binary Search Tree, Kth Smallest Element in a BST

Heaps with heapq

A heap is a tree stored in a flat list, arranged so that the smallest element is always at index 0. Pushing or popping costs O(log n) and peeking at the minimum costs O(1). You never need to build one by hand: the heapq module (already imported on this site) operates on ordinary lists.

import heapq

h = []
for x in [5, 1, 8, 3]:
    heapq.heappush(h, x)
print(h[0])
print(heapq.heappop(h))
print(heapq.heappop(h))

nums = [9, 4, 7]
heapq.heapify(nums)        # turn an existing list into a heap in O(n)
print(nums[0])

1
1
3
4

Remember that only h[0] is meaningful; the rest of the list is in "heap order", not sorted order, so never read h[-1] expecting the maximum.

Max-heap by negation

heapq only provides a min-heap. To get the largest element first, push the negated value and negate it again on the way out:

h = []
for x in [5, 1, 8]:
    heapq.heappush(h, -x)
print(-heapq.heappop(h))

8

Tuples as heap items

When you need to order objects by some key, push tuples. Tuples compare element by element, so the first element is the priority and later elements break ties:

tasks = []
heapq.heappush(tasks, (2, "write tests"))
heapq.heappush(tasks, (1, "fix bug"))
heapq.heappush(tasks, (2, "refactor"))
print(heapq.heappop(tasks))
print(heapq.heappop(tasks))

(1, 'fix bug')
(2, 'refactor')

There is a trap here. If two tuples tie on every element up to an object that does not support <, such as a ListNode, Python raises TypeError. The standard fix is to include a unique integer (an index or a counter) before the object: (node.val, i, node). The index settles ties, so the node itself is never compared.

The bounded heap pattern

Most "k largest / k smallest / k closest / k most frequent" problems use one idea: keep a heap of size at most k and evict whenever it grows to k + 1. To keep the k largest values, use a min-heap, because the element you want to evict is the smallest of the ones kept:

def k_largest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)     # drop the smallest of the k+1
    return sorted(h, reverse=True)

print(k_largest([3, 1, 5, 12, 2, 11], 3))

[12, 11, 5]

After the loop, h[0] is the k-th largest element overall. Symmetrically, to keep the k smallest (or closest) you evict the largest, so you need a max-heap: push the negated key. This runs in O(n log k), which beats sorting when k is much smaller than n, and works on a stream where you never see all the data at once.

For one-off use, heapq.nlargest(k, items, key=...) and heapq.nsmallest implement this pattern for you:

print(heapq.nlargest(2, ["aa", "b", "ccc"], key=len))

['ccc', 'aa']

K-way merge

The last heap pattern merges k sorted sequences. Put the first element of every sequence in a heap, tagged with which sequence it came from. Repeatedly pop the smallest, emit it, and push the next element from the same sequence. Each element enters and leaves the heap once, so merging N elements across k lists costs O(N log k). With linked lists the "next element" is just node.next, and you stitch popped nodes together with a dummy head and a tail pointer, exactly as you did when merging two lists in Phase 2.

Common mistakes

• Forgetting that heapq is a min-heap and popping the wrong end of the problem.
• Reading h[-1] or iterating over h expecting sorted order.
• Pushing bare objects that cannot be compared, then hitting TypeError on the first tie.
• Calling sorted() inside a loop that runs n times: the point of a heap is to avoid that O(n^2 log n) cost.

Practice: Kth Largest Element in a Stream, Top K Frequent Elements, K Closest Points to Origin, Merge K Sorted Lists

Tries

A trie (from retrieval, usually pronounced "try") stores strings so that words with a common prefix share a common path. Each node has one child per possible next character. In Python the simplest representation is a dictionary of dictionaries: the keys are characters and the values are child nodes.

trie = {}
for word in ["car", "cat"]:
    node = trie
    for ch in word:
        node = node.setdefault(ch, {})   # create the child if missing, then step into it
    node["$"] = True                     # mark that a word ends here

print(trie)

{'c': {'a': {'r': {'$': True}, 't': {'$': True}}}}

The "$" marker distinguishes a stored word from a mere prefix: "ca" is on the path to both words, but it is not a word itself, so its node has no "$". Looking something up is the same walk without the setdefault: step through the characters, and if a character is ever missing, the string is not in the trie. Whether you then require the "$" marker at the end is the only difference between "is this a whole word?" and "is this a prefix of some word?".

Why bother, when a Python set already answers "is this word stored?" in O(1)? Because a set cannot answer prefix questions without scanning every entry. A trie answers "does any word start with pre?" in O(3) steps, and can then list all completions by walking the subtree below. That makes tries the structure behind autocomplete, spell-checking, and longest-prefix matching in routers. Word-search puzzles on a grid (Phase 5) also use a trie to prune dead-end paths early.

Common mistakes

• Using the same character as an end marker that could appear in a word. "$" or "#" is safe for lowercase words; for arbitrary strings use a separate boolean attribute on a small TrieNode class instead.
• Returning True from search as soon as the walk succeeds, which makes search behave like starts_with.
• Forgetting that insert must step into the newly created child (node = node.setdefault(...)), not just create it.

Practice: Implement Trie (Prefix Tree)

Checklist

Before moving on to Phase 5, make sure you can:

• Write a recursive function by naming its base case and recursive case, and trace it on paper.
• Explain why deep recursion raises RecursionError and rewrite a recursion with an explicit stack or a loop.
• Halve the problem size per step (as in fast exponentiation) and recognise when that is possible.
• Spot overlapping subproblems and add memoization with a dictionary or lru_cache.
• Read and write the level-order list format and use build_tree / tree_to_list.
• Write pre-order, in-order and post-order traversals, both recursively and with an explicit stack.
• Write a BFS with deque and group the output by level.
• Write the standard tree recursion: handle None, recurse on both children, combine.
• Track a "best so far" value across a recursion with nonlocal.
• State the BST invariant precisely and validate it with bounds or an in-order check.
• Search and insert in a BST, and use in-order traversal to get sorted order.
• Use heapq.heappush, heappop, heapify, nlargest; simulate a max-heap by negation.
• Apply the bounded heap of size k pattern and the k-way merge pattern.
• Push tuples with a tie-breaking index so incomparable objects are never compared.
• Build a trie from nested dictionaries with an end-of-word marker, and tell search from starts_with.