Chapter 5 · Intermediate → Advanced · Prereq: Chapter 4

Trees & Graphs

DFS · BFS · Binary Trees · BST Validation · Diameter · LCA · Graph Traversal · Union-Find · Topological Sort — the most structurally rich chapter, unlocking the widest range of interview problems.

11 Sections 16 Practice Problems Intermediate → Advanced ← Back to Roadmap

Section 1 — Trees & Graphs: The Big Picture

Trees and graphs are the most structurally rich data structures in computer science. They model hierarchical and relational data that cannot be represented with arrays or hash maps alone. Mastering DFS and BFS on trees and graphs unlocks a huge range of interview problems.

1.1 — Tree Terminology

            1          ← root (depth 0)
          /   \
         2     3       ← internal nodes (depth 1)
        / \     \
       4   5     6     ← leaves (depth 2)
      /
     7                 ← leaf (depth 3)

root:    node with no parent (node 1)
leaf:    node with no children — leaves: 5, 6, 7
height:  longest root-to-leaf path = 3 (1→2→4→7)
depth:   distance from root (root depth = 0)
subtree: node + all descendants (subtree at 2: {2,4,5,7})

1.2 — Graph Terminology

Key Graph Concepts

Vertices (V): the nodes; Edges (E): the connections.
Directed (Digraph): edges have direction (arrows); Undirected: edges are bidirectional.
Cycle: path that starts and ends at the same vertex.
DAG: Directed Acyclic Graph — no cycles; used for dependency ordering (topological sort).
Connected: every vertex reachable from every other (undirected graphs).
Tree vs Graph: a tree is a connected, acyclic, undirected graph with exactly V–1 edges.

1.3 — Graph Representations in C++

// ADJACENCY LIST (preferred for sparse graphs)
// Space: O(V+E) | Add edge: O(1) | Find neighbors: O(degree)
int V = 5;
vector<vector<int>> adj(V);   // adj[u] = list of neighbors
adj[0].push_back(1); adj[1].push_back(0); // undirected: add both
// For weighted graphs:
vector<vector<pair<int,int>>> wadj(V);  // {neighbor, weight}
wadj[0].push_back({1, 5});   // edge 0→1 with weight 5

// ADJACENCY MATRIX (dense graphs or quick edge checks)
// Space: O(V^2) | Check edge (u,v): O(1) | Find neighbors: O(V)
vector<vector<int>> mat(V, vector<int>(V, 0));
mat[0][1] = mat[1][0] = 1;   // undirected edge

// EDGE LIST (Kruskal's MST, sorting edges by weight)
vector<tuple<int,int,int>> edges;  // {weight, u, v}
edges.push_back({5, 0, 1});

Section 2 — Tree DFS: Four Traversals

All four tree traversals are O(n) time and O(h) space (h = tree height = recursion depth). The only difference is when you process the current node relative to its children.

Preorder (Root → L → R)

Visit root before children. Output: 1,2,4,5,3. Use: copy tree, serialize, expression prefix.

Inorder (L → Root → R)

Visit root in the middle. Output: 4,2,5,1,3. BST inorder = sorted sequence. Use: validate BST.

Postorder (L → R → Root)

Visit root after children. Output: 4,5,2,3,1. Use: delete tree, evaluate expression tree, compute height/diameter.

Level Order (BFS)

Visit level by level (queue). Output: 1,2,3,4,5. Use: shortest path in tree, level processing, zigzag traversal.

All four traversal templates

struct TreeNode { int val; TreeNode *left, *right; };

// Preorder — O(n) time, O(h) space
void preorder(TreeNode* node, vector<int>& res) {
    if (!node) return;
    res.push_back(node->val);     // ROOT first
    preorder(node->left,  res);
    preorder(node->right, res);
}
// Inorder (BST: gives sorted sequence)
void inorder(TreeNode* node, vector<int>& res) {
    if (!node) return;
    inorder(node->left, res);
    res.push_back(node->val);     // ROOT middle
    inorder(node->right, res);
}
// Postorder (compute height, diameter)
void postorder(TreeNode* node, vector<int>& res) {
    if (!node) return;
    postorder(node->left,  res);
    postorder(node->right, res);
    res.push_back(node->val);     // ROOT last
}
// Level Order (BFS)
vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> res;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int sz = q.size();           // snapshot level size
        vector<int> level;
        while (sz--) {
            TreeNode* n = q.front(); q.pop();
            level.push_back(n->val);
            if (n->left)  q.push(n->left);
            if (n->right) q.push(n->right);
        }
        res.push_back(level);
    }
    return res;
}

All traversalsO(n) Space (DFS)O(h) call stack Space (BFS)O(w) — max width

Section 3 — Tree DFS Patterns

3.1 — Max Depth (Postorder)

// Max depth = 1 + max(leftHeight, rightHeight)
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

3.2 — Diameter (Global Max During Height DFS)

Diameter Insight The diameter through any node = leftHeight + rightHeight. Compute this at every node during the height DFS, tracking the global maximum. Return height (for parent's computation) but update diameter as a side effect.

int diameter = 0;  // global max — must be initialized to 0, not -1
int height(TreeNode* root) {
    if (!root) return 0;
    int L = height(root->left), R = height(root->right);
    diameter = max(diameter, L + R);  // path through this node
    return 1 + max(L, R);             // height for parent
}

3.3 — BST Validation (Pass Min/Max Bounds)

Critical Mistake to Avoid Do NOT validate BST by only comparing parent-child pairs. A node must satisfy constraints from ALL ancestors. The value at node 5 must be less than the parent's value AND all the way up to the root's constraint. Always pass (min, max) bounds down.

bool isValidBST(TreeNode* root, long lo = LONG_MIN, long hi = LONG_MAX) {
    if (!root) return true;
    if (root->val <= lo || root->val >= hi) return false;
    return isValidBST(root->left,  lo, root->val) &&
           isValidBST(root->right, root->val, hi);
}

3.4 — Lowest Common Ancestor

// LCA of BST — exploit BST property O(log n) balanced
TreeNode* lcaBST(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (p->val < root->val && q->val < root->val)
        return lcaBST(root->left,  p, q);
    if (p->val > root->val && q->val > root->val)
        return lcaBST(root->right, p, q);
    return root;  // one on each side (or one IS root) → root is LCA
}
// LCA of general binary tree — postorder DFS
TreeNode* lcaGeneral(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left  = lcaGeneral(root->left,  p, q);
    TreeNode* right = lcaGeneral(root->right, p, q);
    if (left && right) return root;  // p and q in different subtrees
    return left ? left : right;
}

Section 4 — Graph DFS & BFS

DFS vs BFS — When to Use Each

DFS: exploring as far as possible then backtrack. Use for: cycle detection, topological sort, connected components, path existence, tree height/diameter.
BFS: level-by-level exploration. Use for: shortest path in unweighted graph, level-order traversal, multi-source problems (Rotting Oranges).
Key BFS rule: mark nodes visited when enqueued, not when processed. Marking later causes the same node to be enqueued multiple times.

// Graph DFS — O(V+E) time, O(V) space
vector<bool> visited(V, false);
void dfs(int node, vector<vector<int>>& adj) {
    visited[node] = true;
    for (int neighbor : adj[node])
        if (!visited[neighbor]) dfs(neighbor, adj);
}

// Graph BFS — O(V+E) time, O(V) space
void bfs(int start, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    queue<int> q;
    visited[start] = true;   // mark BEFORE enqueue
    q.push(start);
    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (int neighbor : adj[node])
            if (!visited[neighbor]) {
                visited[neighbor] = true;  // mark BEFORE enqueue
                q.push(neighbor);
            }
    }
}

Section 5 — Pattern: Grid DFS (Number of Islands)

Treat a 2D grid as a graph where each cell is a vertex with up to 4 neighbors (up, down, left, right). DFS from each unvisited land cell, sinking the island as you go.

Outer loop: iterate all cells (r,c). If cell is '1' → increment islands, start DFS
DFS: mark cell '0' (sink it) then recurse into 4 neighbors
Always check bounds AND that cell is '1' before recursing
Each cell visited at most twice → O(m×n) total

int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size(), islands = 0;
    // DFS lambda — sinks the island (modifies grid in-place)
    function<void(int,int)> dfs = [&](int r, int c) {
        if (r<0||r>=m||c<0||c>=n||grid[r][c]!='1') return;
        grid[r][c] = '0';  // mark visited by sinking
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    };
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (grid[r][c] == '1') { islands++; dfs(r, c); }
    return islands;
}
// Cannot modify input? Use bool visited[m][n] instead.

TimeO(m×n) SpaceO(m×n) DFS stack

Section 6 — Pattern: Union-Find (Disjoint Set Union)

Union-Find tracks connected components dynamically. Two optimisations make it nearly O(1) per operation: path compression and union by rank.

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // path compression
        return parent[x];
    }
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;       // already same component
        if (rank[px] < rank[py]) swap(px, py); // union by rank
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }
};
// Usage: Redundant Connection — if unite returns false, edge is redundant

Find / UniteO(α(n)) ≈ O(1) SpaceO(V)

Section 7 — Pattern: Topological Sort (Kahn's Algorithm)

Topological sort orders vertices of a DAG such that for every directed edge u→v, u comes before v. If a cycle exists, topological sort is impossible.

// Kahn's Algorithm (BFS-based) — O(V+E) time, O(V) space
vector<int> topoSort(int V, vector<vector<int>>& adj) {
    vector<int> indegree(V, 0);
    for (int u = 0; u < V; u++)
        for (int v : adj[u]) indegree[v]++;
    // Start from all 0-indegree nodes
    queue<int> q;
    for (int i = 0; i < V; i++) if (indegree[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indegree[v] == 0) q.push(v); // indegree drops to 0 → ready
    }
    // If order.size() < V, a cycle exists (Course Schedule: return false)
    return order;
}

Cycle Detection If the output order has fewer than V nodes after Kahn's algorithm completes, the graph contains a cycle — topological sort is impossible. LeetCode 207 (Course Schedule) uses this check to return true/false.

Section 8 — Common Mistakes & Edge Cases

❌ Null root not handled

Always check if (!root) return 0/false/null at the start of every tree function — even before touching root->left or root->right.

❌ BST validated by parent-child only

A value must satisfy constraints from ALL ancestors, not just its direct parent. Always pass (min, max) bounds down recursively.

❌ Height vs Depth confused

Height: measured downward to the farthest leaf. Depth: measured upward from root. Max depth = height of tree.

❌ BFS: mark when processed not enqueued

Mark nodes as visited before pushing to queue. Marking when dequeued causes the same node to be enqueued multiple times → incorrect results or infinite loops.

❌ Grid: access before bounds check

Always validate r>=0 && r<m && c>=0 && c<n BEFORE accessing grid[r][c]. Out-of-bounds access = undefined behaviour.

❌ Union-Find without path compression

Without path compression, trees can become deep and find() degrades to O(n). Always use recursive path compression.

Edge Cases to Test

Empty tree (root = null): return 0 depth, empty list for traversal, 0 diameter
Single node tree: depth = 1, diameter = 0, it is both root and leaf
Skewed tree (all left children): DFS depth = n — risk of stack overflow for n = 10^5. Use iterative DFS.
Grid with all water → 0 islands; grid with all land → 1 island
Disconnected graph: BFS/DFS from one node does NOT reach all nodes. Iterate over ALL unvisited nodes.

Practice Problems

Binary Tree Problems

#	Problem	Pattern	Diff
1	104. Maximum Depth of Binary Tree	Postorder DFS	Easy
2	543. Diameter of Binary Tree	Global max during height DFS	Easy
3	110. Balanced Binary Tree	Return -1 if unbalanced	Easy
4	235. LCA of BST	Exploit BST property	Medium
5	236. LCA of Binary Tree	Postorder DFS — both sides	Medium
6	102. Binary Tree Level Order Traversal	BFS with level size snapshot	Medium
7	98. Validate Binary Search Tree	DFS with (min, max) bounds	Medium
8	230. Kth Smallest Element in BST	Inorder traversal, kth element	Medium

Graph Problems

#	Problem	Pattern	Diff
9	200. Number of Islands	Grid DFS — sink land cells	Medium
10	695. Max Area of Island	DFS returns island size	Medium
11	133. Clone Graph	BFS/DFS + hash map for clones	Medium
12	207. Course Schedule	Cycle detection — Kahn's	Medium
13	210. Course Schedule II	Topological sort order	Medium
14	417. Pacific Atlantic Water Flow	Reverse BFS from both oceans	Medium
15	684. Redundant Connection	Union-Find cycle detection	Medium
16	127. Word Ladder	BFS shortest path — implicit graph	Hard

Section 9 — Iterative Traversals & Morris Inorder

Recursive traversals use O(h) call-stack space. Two alternatives avoid this: explicit-stack iteration (still O(h) but heap-allocated) and Morris Traversal (O(1) space by temporarily threading the tree).

9.1 — Iterative Preorder (Root → L → R)

Key Idea Push root, then repeatedly pop-and-print, pushing right child first so left is processed next (LIFO order gives Root→L→R).

Iterative Preorder — O(n) time, O(h) space

void preOrder(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur || !s.empty()) {
        while (cur) {
            cout << cur->val << " ";   // visit ROOT immediately
            s.push(cur);
            cur = cur->left;           // go left
        }
        cur = s.top(); s.pop();
        cur = cur->right;              // backtrack, try right subtree
    }
}

9.2 — Iterative Inorder (L → Root → R)

Key Idea Same stack pattern as preorder, but print after popping (not while pushing left). This naturally gives left-root-right order, and for a BST produces a sorted sequence.

Iterative Inorder — O(n) time, O(h) space

void inOrder(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur || !s.empty()) {
        while (cur) {
            s.push(cur);
            cur = cur->left;           // drill left first
        }
        cur = s.top(); s.pop();
        cout << cur->val << " ";       // visit ROOT (left already done)
        cur = cur->right;              // then process right subtree
    }
}

9.3 — Morris Inorder Traversal (O(1) Space)

How Morris Traversal Works Instead of a stack, Morris threads the inorder predecessor's right pointer back to the current node — creating a temporary link (thread) to return here after the left subtree finishes. On the second visit the thread is removed and the node is printed. No extra space beyond a few pointers.

Morris Inorder — O(n) time, O(1) space

void morrisInOrder(TreeNode* root) {
    TreeNode* curr = root;
    while (curr) {
        if (!curr->left) {
            cout << curr->val << " ";  // no left child → print and move right
            curr = curr->right;
        } else {
            // Find inorder predecessor: rightmost node in left subtree
            TreeNode* pred = curr->left;
            while (pred->right && pred->right != curr)
                pred = pred->right;

            if (!pred->right) {        // Thread not created yet
                pred->right = curr;    // create thread back to curr
                curr = curr->left;     // descend left
            } else {                   // Thread already exists → second visit
                pred->right = nullptr; // remove thread (restore tree)
                cout << curr->val << " ";
                curr = curr->right;
            }
        }
    }
}

Morris Inorder Traversal walk-through on: [4, 2, 6, 1, 3, 5, 7]

        4
       / \
      2   6
     / \ / \
    1  3 5  7

Step 1: curr=4, pred of 4 is 3 (rightmost of left subtree).
        Thread 3→4. Move curr to 2.
Step 2: curr=2, pred of 2 is 1. Thread 1→2. Move curr to 1.
Step 3: curr=1, no left. Print 1. Move right → follows thread to 2.
Step 4: curr=2, thread found (pred 1→2 exists). Remove thread.
        Print 2. Move right to 3.
Step 5: curr=3, no left. Print 3. Move right → follows thread to 4.
Step 6: curr=4, thread found (pred 3→4). Remove thread.
        Print 4. Move right to 6.
... continues printing 5, 6, 7.

Output: 1 2 3 4 5 6 7  ✓

TimeO(n) Space (Morris)O(1) — no stack/recursion Space (Iterative)O(h) — explicit stack

Section 10 — Tree Serialization & Debug Utilities

These helpers let you build trees from LeetCode-style bracket strings (e.g. "[1,2,3,null,5]"), serialize back to strings, and pretty-print trees visually — invaluable for local testing and debugging.

10.1 — stringToTreeNode (Deserialize)

BFS Construction Algorithm Parse the comma-separated input left-to-right. Use a queue of parent nodes waiting for their children. For each parent, consume the next two tokens as left and right child (skip if "null"). This mirrors LeetCode's level-order representation exactly.

stringToTreeNode — O(n) time & space

void trimLeftTrailingSpaces(string& input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}
void trimRightTrailingSpaces(string& input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}
void trim(string& input) {
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
}

// Parses "[1,2,3,null,5]" → TreeNode*
TreeNode* stringToTreeNode(string input) {
    trim(input);
    input = input.substr(1, input.length() - 2); // strip [ ]
    if (!input.size()) return nullptr;

    stringstream ss; ss.str(input);
    string item;
    getline(ss, item, ',');

    queue<TreeNode*> nodeQ;
    TreeNode* root = new TreeNode(stoi(item));
    nodeQ.push(root);

    while (true) {
        TreeNode* node = nodeQ.front(); nodeQ.pop();

        if (!getline(ss, item, ',')) break;
        trimLeftTrailingSpaces(item);
        if (item != "null") {
            node->left = new TreeNode(stoi(item));
            nodeQ.push(node->left);
        }

        if (!getline(ss, item, ',')) break;
        trimLeftTrailingSpaces(item);
        if (item != "null") {
            node->right = new TreeNode(stoi(item));
            nodeQ.push(node->right);
        }
    }
    return root;
}

10.2 — treeNodeToString (Serialize)

treeNodeToString — O(n) time & space

// Serializes a tree to "[1,2,3,null,5,null,null]" (LeetCode format)
string treeNodeToString(TreeNode* root) {
    if (!root) return "[]";
    string output;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        if (!node) { output += "null, "; continue; }
        output += to_string(node->val) + ", ";
        q.push(node->left);
        q.push(node->right);
    }
    return "[" + output.substr(0, output.length() - 2) + "]";
}

10.3 — prettyPrintTree (Visual Debugger)

How it Works Recursively prints the right subtree first (top of console = rightmost node), then the current node, then the left subtree. Each level is indented with box-drawing characters (└──, ┌──, │) to show the tree shape.

prettyPrintTree — example output for [4,2,6,1,3,5,7]

void prettyPrintTree(TreeNode* node, string prefix = "", bool isLeft = true) {
    if (!node) { cout << "Empty tree"; return; }
    if (node->right)
        prettyPrintTree(node->right, prefix + (isLeft ? "│   " : "    "), false);
    cout << prefix + (isLeft ? "└── " : "┌── ") + to_string(node->val) + "\n";
    if (node->left)
        prettyPrintTree(node->left,  prefix + (isLeft ? "    " : "│   "), true);
}

/*  Output for [4,2,6,1,3,5,7]:
    ┌── 7
│   ┌── 6
│       └── 5
└── 4
    ┌── 3
    └── 2
        └── 1
*/

10.4 — Putting It All Together (main driver)

Local test driver — reads tree strings from stdin

int main() {
    string line;
    while (getline(cin, line)) {
        TreeNode* root = stringToTreeNode(line);
        prettyPrintTree(root);
        cout << "Pre Order:  [ "; preOrder(root);        cout << "]\n";
        cout << "In Order:   [ "; morrisInOrder(root);   cout << "]\n";
        cout << "Post Order: [ "; postOrderTraversal(root); cout << "]\n";
        cout << "Serialized: " << treeNodeToString(root) << "\n\n";
    }
    return 0;
}
// Input example:  [1,2,3,4,5,null,6]
// Pre Order:  [ 1 2 4 5 3 6 ]
// In Order:   [ 4 2 5 1 3 6 ]
// Post Order: [ 4 5 2 6 3 1 ]

Serialize / DeserializeO(n) prettyPrintTreeO(n) SpaceO(n) queue / O(h) recursion