Trees, Binary Search Trees, and Heaps

Trees Are Just Nested Boxes

A tree is a value plus a list of subtrees. That's it. The intimidation comes from the vocabulary — root, node, leaf, parent, child — but the shape is dead simple, and once you see it, half the "hard" interview questions turn into three lines of recursion.

In Python you rarely need a fancy class. A binary tree node is this:

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

Trees show up everywhere real: your filesystem, the DOM, JSON you parse, the abstract syntax tree your linter walks. When a problem has "hierarchy" or "contains" in it, reach for a tree before you reach for anything clever.

The one thing to internalize: a tree with n nodes and height h. If it's balanced, h ≈ log n. If it's a straight line (every node has one child), h = n and you've built a linked list wearing a tree costume. That difference is the whole chapter.

Traversal: Depth-First vs Breadth-First

There are two ways to visit every node, and you should be able to write both cold.

Depth-first (DFS) goes deep before wide. It's recursion, and the three orders differ only by when you touch the current node:

def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.val)      # visit between children
    inorder(node.right)

Move that print above both calls and you have preorder; below both, postorder. For a binary search tree, inorder spits values out sorted — that's the trick behind half of BST problems.

Breadth-first (BFS) goes level by level, using a queue instead of the call stack:

from collections import deque

def bfs(root):
    if not root:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)

Pick by the question. "Shortest path in an unweighted structure," "level order," "closest to the root" — BFS. "Does a path exist," "sum along branches," anything naturally recursive — DFS. Both are O(n) time. DFS costs O(h) stack space; BFS costs O(width), which for the bottom level of a balanced tree is n/2. Neither is free.

One warning: Python's recursion limit is ~1000. On a deep or degenerate tree, recursive DFS blows the stack. Know how to rewrite it with an explicit stack when the input is adversarial.

Binary Search Trees: Fast Until They Aren't

A BST adds one rule: everything in the left subtree is smaller, everything in the right is larger. That invariant lets you search by walking down one branch, halving your options each step:

def search(node, target):
    while node:
        if target == node.val:
            return node
        node = node.left if target < node.val else node.right
    return None

Search, insert, and delete are all O(h). When the tree is balanced, that's O(log n) — a million nodes in twenty steps. Beautiful.

Here's the catch nobody warns you about: insert sorted data into a plain BST and it degrades into a linked list. Insert 1, 2, 3, 4, 5 in order and every node hangs off the right of the last. Your O(log n) is now O(n), and your "efficient" tree is slower than an array.

The real fix is self-balancing trees — red-black and AVL trees rotate nodes on insert to keep height near log n. That's what std::map and Java's TreeMap use under the hood. You should understand they exist and why, but in Python you almost never hand-roll one. For interviews, know the failure mode and the name of the cure. For real code, if you need sorted-and-fast, reach for the sortedcontainers library's SortedList — it's battle-tested and you won't introduce a rotation bug at 2am.

If you want a deeper Python refresher before the heavier chapters, the DSA in Python course covers this material with runnable exercises.

Heaps: The Priority Queue You'll Actually Use

Forget BSTs for a second. Most of the time you don't need the whole thing sorted — you just need the smallest thing, right now, fast. That's a heap, and Python ships one in the standard library: heapq.

A heap gives you the min element in O(1) and push/pop in O(log n). It does not keep everything sorted, which is exactly why it's cheaper than a BST for this job.

import heapq

nums = [5, 1, 8, 3, 2]
heapq.heapify(nums)          # O(n), in place
heapq.heappush(nums, 0)
smallest = heapq.heappop(nums)   # 0

heapq is a min-heap. Want the max? Push negatives and negate on the way out. Want to sort by a custom key? Push tuples — (priority, item) — and it orders by the first element.

Three patterns cover almost every heap interview question:

Top-K. To find the K largest of a stream, keep a min-heap of size K. Push each item; if the heap grows past K, pop the smallest. Whatever survives is your top K, in O(n log K) — far better than sorting everything when K is small.

def top_k(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)     # drop the smallest
    return heap

Merge sorted streams. heapq.merge() lazily merges any number of sorted iterables — perfect for external sorting when data doesn't fit in memory.

Streaming median. Keep two heaps: a max-heap of the lower half, a min-heap of the upper half, balanced to differ in size by at most one. The median is a top or an average of the two tops, updated in O(log n) per new number. It looks like a party trick; it's the standard answer, and worth drilling until you can write it without thinking.

The instinct to reach for is this: whenever a problem says "K largest," "K smallest," "K closest," "most frequent," or "running median," a heap is almost certainly the intended tool. Recognize the phrasing and you've already solved it.