📝 Blog 8: DP on Trees & Graphs 🌳🔗

(Dynamic Programming Beyond Arrays)

---

🔍 Why DP on Trees & Graphs?

So far, we solved DP on arrays, strings, intervals. But real-world data often forms hierarchies (trees) or networks (graphs).

Here, subproblems are no longer just [i…j] or prefixes—they’re subtrees or graph components.

---

⚡ Key Idea

• On Trees → DP is usually done with DFS + memoization.
• On Graphs → DP often relies on topological ordering (for DAGs) or cycle handling.

---

🌳 DP on Trees

🏆 Patterns

1️⃣ Tree DP (Post-order DFS)

Each node’s result depends on its children.

Example: Diameter of a Tree (Longest Path)

class TreeDiameter {
    int diameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return diameter;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        diameter = Math.max(diameter, left + right);
        return 1 + Math.max(left, right);
    }
}

• dfs(node) returns height.
• Global diameter updates from children.

---

2️⃣ Maximum Path Sum in Binary Tree

class MaxPathSum {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));
        maxSum = Math.max(maxSum, left + right + node.val);
        return node.val + Math.max(left, right);
    }
}

• Notice DP relation:

  • dp[node] = node.val + max(dp[left], dp[right])

---

3️⃣ Tree DP with Subtree Inclusion/Exclusion (Classic “Tree Knapsack”)

📌 Problem: Maximum sum of nodes with constraint → cannot take both parent & child.

class HouseRobberTree {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0,0};
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        // res[0] = max sum if NOT taking node
        // res[1] = max sum if taking node
        return new int[]{
            Math.max(left[0], left[1]) + Math.max(right[0], right[1]),
            node.val + left[0] + right[0]
        };
    }
}

---

4️⃣ LCA + DP on Trees

Lowest Common Ancestor (LCA) is a preprocessing DP using binary lifting.

class LCA {
    int LOG = 20;
    int[][] up;
    int[] depth;
    List<Integer>[] adj;
    public LCA(int n, int root, List<Integer>[] adj) {
        this.adj = adj;
        up = new int[n][LOG];
        depth = new int[n];
        dfs(root, root);
    }
    private void dfs(int node, int parent) {
        up[node][0] = parent;
        for (int i = 1; i < LOG; i++) {
            up[node][i] = up[up[node][i-1]][i-1];
        }
        for (int nei : adj[node]) {
            if (nei == parent) continue;
            depth[nei] = depth[node] + 1;
            dfs(nei, node);
        }
    }
    public int query(int a, int b) {
        if (depth[a] < depth[b]) { int tmp=a; a=b; b=tmp; }
        int diff = depth[a] - depth[b];
        for (int i = LOG-1; i >= 0; i--) {
            if (((diff >> i) & 1) == 1) a = up[a][i];
        }
        if (a == b) return a;
        for (int i = LOG-1; i >= 0; i--) {
            if (up[a][i] != up[b][i]) {
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    }
}

• DP preprocessing stores ancestors at 2^i distance.
• Query runs in O(logN).

---

🔗 DP on Graphs

🏆 Patterns

1️⃣ Longest Path in a DAG

class LongestPathDAG {
    public int longestPath(int n, int[][] edges) {
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        int[] indegree = new int[n];
        for (int[] e : edges) {
            adj[e[0]].add(e[1]);
            indegree[e[1]]++;
        }

        Queue<Integer> q = new LinkedList<>();
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) if (indegree[i]==0) q.add(i);

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj[u]) {
                dp[v] = Math.max(dp[v], dp[u] + 1);
                if (--indegree[v] == 0) q.add(v);
            }
        }
        int ans = 0;
        for (int d : dp) ans = Math.max(ans, d);
        return ans;
    }
}

• Topological sort ensures dependencies are resolved first.

---

2️⃣ Shortest Path in DAG (DP form of Dijkstra)

class ShortestPathDAG {
    public int[] shortestPath(int n, int[][] edges, int src) {
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) adj[e[0]].add(new int[]{e[1], e[2]});

        int[] topo = topoSort(n, adj);
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        for (int u : topo) {
            if (dist[u] == Integer.MAX_VALUE) continue;
            for (int[] e : adj[u]) {
                int v = e[0], w = e[1];
                dist[v] = Math.min(dist[v], dist[u] + w);
            }
        }
        return dist;
    }
    private int[] topoSort(int n, List<int[]>[] adj) {
        int[] indegree = new int[n];
        for (int u = 0; u < n; u++) {
            for (int[] e : adj[u]) indegree[e[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) if (indegree[i]==0) q.add(i);

        int[] order = new int[n]; int idx=0;
        while (!q.isEmpty()) {
            int u = q.poll();
            order[idx++] = u;
            for (int[] e : adj[u]) if (--indegree[e[0]]==0) q.add(e[0]);
        }
        return order;
    }
}

---

3️⃣ Floyd-Warshall (All-Pairs Shortest Path)

class FloydWarshall {
    public void floydWarshall(int[][] dist) {
        int n = dist.length;
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != 1e9 && dist[k][j] != 1e9) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
    }
}

• This is DP on graph nodes as intermediates.

---

🔑 Key Insights

• Tree DP: Usually DFS-based, bottom-up.
• Graph DP: Usually topological-order DP for DAGs or matrix DP (Floyd-Warshall).

• Subproblems:

  • For trees → subtrees.
  • For graphs → nodes + edges constraints.

---

🎯 Real-Life Applications

• Network routing (shortest path).
• Compilers & parsing (tree DP).
• Game AI (minimax on trees).
• Data indexing (optimal BST).

---