Trees model hierarchy and enable O(log n) operations when balanced. Learn binary trees and traversals, binary search trees, self-balancing trees at a high level, and the heap — the structure behind priority queues.
A binary tree is nodes each linked to up to two children, modeling hierarchy. You visit its nodes by traversal, and the order matters: in-order, pre-order, and post-order are depth-first variants distinguished by when you process the current node relative to its children, while level-order (breadth-first) visits row by row using a queue. These traversals underpin nearly every tree algorithm.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
# depth-first traversals differ only in WHEN you visit the node:
def inorder(node): # left, NODE, right -> sorted order for a BST
if node:
inorder(node.left); print(node.val); inorder(node.right)
def preorder(node): # NODE, left, right -> copy/serialize a tree
if node:
print(node.val); preorder(node.left); preorder(node.right)
def postorder(node): # left, right, NODE -> delete/evaluate children first
if node:
postorder(node.left); postorder(node.right); print(node.val)Level-order traversal visits a tree row by row, top to bottom, using a queue — the same breadth-first idea you will use on graphs. It answers questions about depth and levels (the shortest path in an unweighted tree, the nodes at each level) that depth-first traversal handles awkwardly. It is the tree version of BFS.
from collections import deque
def level_order(root):
if not root: return []
result, q = [], deque([root])
while q:
level = []
for _ in range(len(q)): # process one full level at a time
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
result.append(level)
return result
# uses a QUEUE (BFS). Great for "levels", depth, or shortest path in a tree.A binary search tree keeps its nodes ordered: every left descendant is smaller and every right descendant is larger. That invariant lets you search, insert, and delete in O(h) where h is the height — O(log n) when the tree is balanced. An in-order traversal of a BST yields sorted output, which is why the structure is so useful.
# BST invariant: left subtree < node < right subtree
def search(node, target):
while node:
if target == node.val: return node
node = node.left if target < node.val else node.right # discard half
return None # O(h): O(log n) if balanced
def insert(node, val):
if not node: return TreeNode(val)
if val < node.val: node.left = insert(node.left, val)
else: node.right = insert(node.right, val)
return node
# in-order traversal of a BST prints values in SORTED order.A BST is only O(log n) if it stays balanced; insert already-sorted data into a naive BST and it degenerates into a linked list with O(n) operations. Self-balancing trees — AVL and red-black trees — automatically rotate to keep height logarithmic, while B-trees (and B+ trees) keep many keys per node to minimize disk reads, which is why databases and filesystems use them for indexes.
The problem: a plain BST can degenerate.
insert 1,2,3,4,5 in order -> a "tree" that's really a linked list -> O(n).
Self-balancing trees fix this by restructuring on insert/delete:
AVL tree strict height balance via rotations -> fast lookups
Red-Black tree looser balance, faster updates -> used in language libs
(e.g. many "ordered map" implementations)
B-tree / B+ tree many keys per node -> few disk reads -> DATABASE + FILE
SYSTEM indexes (see the PostgreSQL course)
You rarely implement these; you must know WHY they exist: guaranteed
O(log n) even on adversarial input.A heap is a tree-shaped array that keeps the smallest (or largest) element instantly accessible at the root, with O(log n) insert and remove and O(1) peek. It implements a priority queue — "always give me the most important item next" — which powers Dijkstra’s shortest path, scheduling, and top-k problems. Python’s heapq is a ready-made min-heap.
import heapq
h = []
heapq.heappush(h, 5) # O(log n)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
heapq.heappop(h) # 1 — always removes the SMALLEST, O(log n)
h[0] # peek at the min — O(1)
# "k largest" without sorting everything — O(n log k):
def k_largest(nums, k):
return heapq.nlargest(k, nums)
# a heap = a priority queue. It's the engine behind Dijkstra (next lesson),
# schedulers, and top-k / "two heaps" (median) problems.