Trees and Graphs

Trees are the recursive backbone of every serious data structure — file systems, DOMs, ASTs, database indexes, search structures. Graphs generalize trees and unlock scheduling, routing, dependency resolution, and social-network problems. If you know four traversal patterns (preorder / inorder / postorder / level) plus DFS + BFS + Union-Find, you can attack the majority of tree/graph study problems.

Java is graceful for trees (recursion works) and slightly awkward for graphs (no built-in graph class; you build Map<T, List<T>> by hand). This file covers what you write yourself, what you reuse from the stdlib, and which patterns own which problems.

1. Binary tree — the node type you’ll write 200 times

public static class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { this.val = v; }
    TreeNode(int v, TreeNode l, TreeNode r) { this.val = v; this.left = l; this.right = r; }
}

LeetCode-style. Field-visible for terse code. Own projects should encapsulate; study code should be short.

The four traversals

Preorder = root, left, right. Inorder = left, root, right. Postorder = left, right, root. Level-order = BFS.

Inorder is the special one: on a BST it yields sorted order.

Recursive template:

void preorder(TreeNode n, List<Integer> out) {
    if (n == null) return;
    out.add(n.val);
    preorder(n.left, out);
    preorder(n.right, out);
}

Iterative inorder (using a stack) — the one that’s actually tested:

List<Integer> inorder(TreeNode root) {
    var out = new ArrayList<Integer>();
    var stack = new ArrayDeque<TreeNode>();
    var cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        out.add(cur.val);
        cur = cur.right;
    }
    return out;
}

Level order (BFS):

List<List<Integer>> levelOrder(TreeNode root) {
    var out = new ArrayList<List<Integer>>();
    if (root == null) return out;
    var q = new ArrayDeque<TreeNode>();
    q.offer(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        var level = new ArrayList<Integer>(sz);
        for (int i = 0; i < sz; i++) {
            var n = q.poll();
            level.add(n.val);
            if (n.left  != null) q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
        out.add(level);
    }
    return out;
}

The int sz = q.size() snapshot at the top of each level is critical for level-grouped output.

---

2. Binary Search Tree (BST)

Invariant: for every node, left subtree values < node value < right subtree values.

Insert (recursive)

TreeNode insert(TreeNode root, int v) {
    if (root == null) return new TreeNode(v);
    if (v < root.val) root.left  = insert(root.left,  v);
    else if (v > root.val) root.right = insert(root.right, v);
    return root;
}

Search

TreeNode find(TreeNode root, int v) {
    while (root != null && root.val != v) root = (v < root.val) ? root.left : root.right;
    return root;
}

Delete — the one that’s actually tricky

Three cases: leaf (drop it), one child (bypass), two children (replace with in-order successor — leftmost of right subtree — then delete that successor from the right).

TreeNode delete(TreeNode root, int v) {
    if (root == null) return null;
    if (v < root.val)       root.left  = delete(root.left, v);
    else if (v > root.val)  root.right = delete(root.right, v);
    else {
        if (root.left == null)  return root.right;
        if (root.right == null) return root.left;
        // two children: find in-order successor
        TreeNode succ = root.right;
        while (succ.left != null) succ = succ.left;
        root.val = succ.val;
        root.right = delete(root.right, succ.val);
    }
    return root;
}

⚠️ What most people get wrong

They assume the BST is balanced. A BST built by inserting 1..n in order degenerates into a linked list — O(n) for every operation, not O(log n). If balancing matters, use TreeMap / TreeSet, which are red-black trees, guaranteed O(log n).

Self-balancing BSTs (AVL, red-black) are worth understanding conceptually: rotations, invariants. You will almost never implement them in an study. If asked, describe them, and reach for TreeMap.

---

3. Tree DFS patterns you must know

Pattern A — top-down parameter passing (path sum, max depth):

int maxDepth(TreeNode n) {
    if (n == null) return 0;
    return 1 + Math.max(maxDepth(n.left), maxDepth(n.right));
}

Pattern B — bottom-up return value (diameter, invert, balanced check):

// returns depth; updates a class-level or array-wrapped answer
int depth(TreeNode n, int[] best) {
    if (n == null) return 0;
    int L = depth(n.left,  best);
    int R = depth(n.right, best);
    best[0] = Math.max(best[0], L + R);   // diameter through n
    return 1 + Math.max(L, R);
}

Pattern C — serialize / deserialize with preorder + null markers.

Pattern D — lowest common ancestor (LCA) for binary trees:

TreeNode lca(TreeNode n, TreeNode p, TreeNode q) {
    if (n == null || n == p || n == q) return n;
    TreeNode L = lca(n.left,  p, q);
    TreeNode R = lca(n.right, p, q);
    if (L != null && R != null) return n;
    return (L != null) ? L : R;
}

---

4. Tries (prefix trees)

Worth knowing for autocomplete, word-search, and “replace words” type problems.

public class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean end;
}

void insert(TrieNode root, String w) {
    var cur = root;
    for (char c : w.toCharArray()) {
        int i = c - 'a';
        if (cur.children[i] == null) cur.children[i] = new TrieNode();
        cur = cur.children[i];
    }
    cur.end = true;
}

boolean search(TrieNode root, String w) {
    var cur = root;
    for (char c : w.toCharArray()) {
        cur = cur.children[c - 'a'];
        if (cur == null) return false;
    }
    return cur.end;
}

For Unicode or general alphabet, use Map<Character, TrieNode> instead of the 26-array. Array is faster for lowercase-only.

---

5. Graph representation — adjacency list wins

Map<Integer, List<Integer>> adj = new HashMap<>();
for (int i = 0; i < n; i++) adj.put(i, new ArrayList<>());
for (int[] e : edges) {
    adj.get(e[0]).add(e[1]);
    adj.get(e[1]).add(e[0]);   // omit for directed
}

Or, if vertices are 0..n-1 and dense enough, List<List<Integer>> adj = new ArrayList<>(); with n empty lists. This is often what LeetCode gives you.

Weighted: use int[]{to, weight} or a small record Edge(int to, int weight).

Adjacency matrix (boolean[n][n] or int[n][n]) is only sensible for dense graphs or when you need O(1) edge existence checks. Uses O(n²) space.

---

6. BFS and DFS on graphs

BFS — shortest path in unweighted graphs

int shortestPath(Map<Integer, List<Integer>> adj, int src, int dst) {
    var q = new ArrayDeque<Integer>();
    var dist = new HashMap<Integer, Integer>();
    q.offer(src);
    dist.put(src, 0);
    while (!q.isEmpty()) {
        int u = q.poll();
        if (u == dst) return dist.get(u);
        for (int v : adj.getOrDefault(u, List.of())) {
            if (!dist.containsKey(v)) {
                dist.put(v, dist.get(u) + 1);
                q.offer(v);
            }
        }
    }
    return -1;
}

Key rule: mark visited on ENQUEUE, not on dequeue. Otherwise you enqueue the same node many times through different parents and the queue explodes.

DFS — iterative and recursive

Recursive is shorter; iterative avoids stack overflow on deep graphs.

void dfs(int u, Map<Integer, List<Integer>> adj, Set<Integer> seen) {
    if (!seen.add(u)) return;
    for (int v : adj.getOrDefault(u, List.of())) dfs(v, adj, seen);
}

JVM default stack size crashes around depth ~10–20k for typical frame sizes. For graphs that deep, use an explicit Deque<Integer> stack.

Cycle detection

• Undirected: DFS with parent tracking; if you revisit a neighbor that isn’t the parent, cycle exists.

• Directed: DFS with three-color marking (WHITE=unvisited, GRAY=in current path, BLACK=done). A GRAY-to-GRAY edge is a back edge = cycle.

Topological sort (directed acyclic graphs)

Kahn’s algorithm (BFS-based, most iterative-friendly):

List<Integer> topo(int n, int[][] edges) {
    var adj = new ArrayList<List<Integer>>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }
    var q = new ArrayDeque<Integer>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
    var order = new ArrayList<Integer>();
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
    }
    return order.size() == n ? order : List.of();   // empty on cycle
}

Course Schedule / Course Schedule II / Alien Dictionary are all this pattern.

Dijkstra — shortest path with non-negative weights

int dijkstra(int n, List<int[]>[] adj, int src, int dst) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    var pq = new PriorityQueue<int[]>(Comparator.comparingInt(a -> a[0]));  // {dist, node}
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (u == dst) return d;
        if (d > dist[u]) continue;                     // stale entry
        for (int[] nb : adj[u]) {
            int v = nb[0], w = nb[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return -1;
}

Use BFS (not Dijkstra) when all weights are 1 — it’s O(V+E) vs Dijkstra’s O((V+E) log V). For negative weights, use Bellman-Ford. For all-pairs, Floyd-Warshall (O(V³), tiny graphs only).

---

7. Union-Find (Disjoint Set Union, DSU)

The cheat code for connectivity problems. Two operations, both essentially O(α(n)) which is effectively O(1):

public class DSU {
    private final int[] parent, rank;
    public DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // path compression (halving)
            x = parent[x];
        }
        return x;
    }
    public boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank[ra] < rank[rb]) { parent[ra] = rb; }
        else if (rank[ra] > rank[rb]) { parent[rb] = ra; }
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    }
}

When to reach for DSU:

• Number of connected components (count find(i) == i for all i, or count union failures)

• Minimum Spanning Tree (Kruskal’s)

• “Are these two things in the same group?” queries interleaved with unions

• Redundant Connection / Accounts Merge / Number of Islands II

---

8. When TreeMap / TreeSet beats HashMap / HashSet

• Range queries: subMap(from, to), headMap, tailMap.

• Floor / ceiling: floorKey(k) = greatest key ≤ k, ceilingKey(k) = smallest key ≥ k. Perfect for “nearest neighbor” over ordered keys.

• Sorted iteration: iterating a TreeMap gives keys in order.

• First / last: always available.

Cost: O(log n) instead of O(1) for basic operations. Worth it when you actually use the ordering. Otherwise stick with HashMap.

Real study signal: “design a system to find the closest available meeting slot” → TreeMap<LocalDateTime, ...> + ceilingKey. This is the moment TreeMap earns its keep.

---

9. Complexity summary

Structure / Algorithm	Time	Space
BST search / insert / delete (balanced)	O(log n)	O(1) per op
BST search / insert / delete (skewed)	O(n) worst	O(1)
Tree DFS (any order)	O(n)	O(h) stack, h = height
Tree BFS	O(n)	O(w) queue, w = max width
Trie insert / search	O(L), L = word length	O(A · N) total
Graph BFS / DFS	O(V + E)	O(V)
Kahn topo sort	O(V + E)	O(V)
Dijkstra (binary heap)	O((V + E) log V)	O(V)
DSU find + union with compression + rank	~O(α(n)) per op	O(n)

---

Practice slate

Trees: Invert Binary Tree, Maximum Depth, Diameter, Balanced Binary Tree, Same Tree, Subtree of Another Tree, Validate BST, LCA of BST, LCA of Binary Tree, Serialize/Deserialize Binary Tree, Kth Smallest in BST, Level Order Traversal. Tries: Implement Trie, Word Search II, Design Add-and-Search Words. Graphs: Number of Islands, Clone Graph, Course Schedule, Course Schedule II, Pacific Atlantic Water Flow, Word Ladder, Rotting Oranges, Network Delay Time (Dijkstra), Redundant Connection (DSU), Accounts Merge (DSU).

~25 problems, 15–20 hours. Do the trees first — they warm up the recursion pattern that graph DFS reuses.

---

Return to README.md · Next: 04_sorting_and_searching.md