Lesson 5 of 6

Trees and graphs

2 min read

Binary tree traversals

python

def inorder(node, out):            # left, node, right: sorted order for a BST
    if not node: return
    inorder(node.left, out); out.append(node.val); inorder(node.right, out)

def max_depth(node):
    if not node: return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

Level-order (BFS) with a queue:

python

from collections import deque
def level_order(root):
    if not root: return []
    out, q = [], deque([root])
    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

Binary search tree: left subtree < node < right subtree. Search, insert and delete are O(h): O(log n) when balanced, O(n) when it degenerates into a line. Validate a BST by passing allowed (low, high) bounds down, not by only comparing with direct children.

Recursion pattern for most tree problems: "what do I need from my left and right children to answer for this node?" (height, diameter, balanced check, lowest common ancestor, path sums).

Graphs

Represent with an adjacency list: graph = {node: [neighbours]}.

BFS: shortest path in an unweighted graph, levels, "minimum steps".
DFS: explore everything, connected components, cycle detection, topological order.

python

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != "1": return
        grid[r][c] = "0"
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): sink(r + dr, c + dc)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1": count += 1; sink(r, c)
    return count

Topological sort (course schedule: can you finish all courses given prerequisites?): Kahn's algorithm, repeatedly take nodes with in-degree 0. If you can't take all nodes, there's a cycle.

Dijkstra for weighted shortest paths (non-negative weights): a min-heap of (distance, node). Union-Find (disjoint set) for connectivity and Kruskal's minimum spanning tree.

Problems to practise

Maximum Depth, Invert Binary Tree, Same Tree, Level Order Traversal, Validate BST, Lowest Common Ancestor, Diameter of Binary Tree, Number of Islands, Clone Graph, Course Schedule, Rotting Oranges, Network Delay Time.

← Previous Next →