Path DP

The Hardest Subtlety in Tree DP

Subtree DP (Lesson 1) has a clean structure: the answer at each node depends only on its children's answers, and you return one value upward. Path DP breaks this cleanness, and understanding why is the point of this lesson.

The issue: a path through a node might use both the left and right children. But you can only return one direction to the parent — the parent can't use both of your arms.

This creates a split:

The return value (what you send upward) is the best single-arm path through this node.
The answer candidate (what you compare against the global best) is the best through-both-arms path at this node.

You saw this split when computing diameter and max path sum earlier in the course. Now we formalize it as Path DP.

Revisiting Diameter as DP

Problem: Find the diameter of a binary tree — the longest path between any two nodes (measured in edges).

At each node, the longest path through it uses the deepest point in the left subtree and the deepest point in the right subtree. The depth of each side is the "arm length."

\(\text{dp}[\text{node}]\) = height of the subtree rooted at node (longest downward path).

The answer candidate at each node is \(\text{dp}[\text{left}] + \text{dp}[\text{right}]\) — the path going through both children.

The return value to the parent is \(1 + \max(\text{dp}[\text{left}],\ \text{dp}[\text{right}])\) — the single longest arm.

Node	dp[left]	dp[right]	Answer candidate (left + right)	Return (1 + max)
4	0	0	0	1
5	0	0	0	1
2	1	1	2	2
3	0	0	0	1
1	2	1	3	3

The global best answer candidate is 3 (at node 1). The path is 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3).

The return value is NOT the answer. The answer is a side effect. This is the defining feature of path DP. You track the global best separately because the "through both children" path can't be extended by the parent.

New Problem: Longest Univalue Path (LC 687)

Problem: Find the length of the longest path in the tree where every node on the path has the same value. The length is measured in edges.

The longest univalue path is 4 → 4 → 4 (through node 4's left subtree), length 2.

This is path DP with a twist: you can only extend a path if the child's value matches the current node's value.

DP definition: \(\text{dp}[\text{node}]\) = length of the longest univalue arm extending downward from this node (where all values match node's value).

At each node: - Check if left child has the same value. If yes, \(\text{extendLeft} = \text{dp}[\text{left}] + 1\). If no, \(\text{extendLeft} = 0\). - Same for right child. - Answer candidate: \(\text{extendLeft} + \text{extendRight}\) (path going through this node using both arms). - Return value: \(\max(\text{extendLeft},\ \text{extendRight})\) (best single arm for the parent).

Full Trace

Node	Value	Left child val	Right child val	extendLeft	extendRight	Answer candidate	Return
4 (leaf, left-left)	4	—	—	0	0	0	0
4 (leaf, left-right)	4	—	—	0	0	0	0
4 (internal)	4	4 (match)	4 (match)	0 + 1 = 1	0 + 1 = 1	1 + 1 = 2	max(1, 1) = 1
5 (leaf, right-right)	5	—	—	0	0	0	0
5 (internal)	5	—	5 (match)	0	0 + 1 = 1	0 + 1 = 1	1
1 (root)	1	4 (no match)	5 (no match)	0	0	0	0

Global best answer candidate: 2 (at the internal node 4). The path is left-leaf-4 → 4 → right-leaf-4.

Verify: That path has values [4, 4, 4], all equal, length 2 edges. Correct.

The Two-Value Return Pattern

Path DP always produces two values at each node:

The arm — the longest extending path that can be continued by the parent.
The bridge — the through-both-children path that is a complete answer candidate.

You only return the arm. The bridge updates a global variable (or you track it separately). This pattern appears in:

Diameter (arm = depth, bridge = left depth + right depth)
Max path sum (arm = max one-sided sum, bridge = left + right + node value)
Longest univalue path (arm = matching extension, bridge = both matching extensions)

The structure is always:

solve(node):
    leftArm = solve(left)
    rightArm = solve(right)
    bridge = f(leftArm, rightArm, node)
    globalBest = max(globalBest, bridge)
    arm = g(leftArm, rightArm, node)
    return arm

Where \(f\) combines both arms (the answer candidate) and \(g\) picks the better single arm (the return value).

The Code

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

int longestPath = 0;

int solve(TreeNode* root) {
    if (!root) return 0;

    int leftArm = solve(root->left);
    int rightArm = solve(root->right);

    int extendLeft = 0;
    if (root->left && root->left->val == root->val) {
        extendLeft = leftArm + 1;
    }

    int extendRight = 0;
    if (root->right && root->right->val == root->val) {
        extendRight = rightArm + 1;
    }

    longestPath = max(longestPath, extendLeft + extendRight);

    return max(extendLeft, extendRight);
}

int longestUnivaluePath(TreeNode* root) {
    longestPath = 0;
    solve(root);
    return longestPath;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(4);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(5);

    cout << longestUnivaluePath(root) << "\n";
    return 0;
}

Complexity: \(O(n)\) time, \(O(h)\) space.

Subtree DP vs Path DP

	Subtree DP	Path DP
Return value IS the answer?	Yes	No
Global variable needed?	No	Yes (for the bridge)
Number of values at each node	1	2 (arm + bridge)
Examples	Subtree sum, subtree size, MIS	Diameter, max path sum, univalue path

If the answer can only live inside a subtree, use subtree DP. If the answer is a path that might cross from left to right through a node, use path DP.

Try It

Input: [1, 4, 5, 4, 4, null, 5]
Output: 2

Predict before running: What if every node in the tree has the same value? Then every edge extends the path. The longest path is the diameter. For a balanced tree of \(n\) nodes, that's roughly \(2 \log n\).

Challenge: LC 124 — Binary Tree Maximum Path Sum. Each node has an integer value (possibly negative). Find the path with the maximum sum. This is the same path DP pattern — what changes in the combine step?

Challenge 2: Can you solve longest univalue path without a global variable? Return a pair (arm, bestBridge) from each call. The parent takes the max of all bridges seen in the subtree.

Problems

Problem	Link	Difficulty
LC 687 — Longest Univalue Path	leetcode.com/problems/longest-univalue-path	Medium
LC 124 — Binary Tree Maximum Path Sum	leetcode.com/problems/binary-tree-maximum-path-sum	Hard
LC 543 — Diameter of Binary Tree	leetcode.com/problems/diameter-of-binary-tree	Easy
LC 549 — Binary Tree Longest Consecutive Sequence II	leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii	Medium
LC 1245 — Tree Diameter	leetcode.com/problems/tree-diameter	Medium
CF 161D — Distance in Tree	codeforces.com/problemset/problem/161/D	Medium

Beyond This Chapter: Rerooting

There's one more tree DP technique that doesn't fit here: the rerooting technique. It answers questions like "what is the sum of distances from node \(v\) to all other nodes — for EVERY node \(v\)?" (LC 834).

The idea: compute the answer for root node 1 using standard postorder. Then "reroot" the tree to each adjacent node in \(O(1)\) per edge, adjusting the answer as the root shifts. Total: \(O(n)\) for all nodes, not \(O(n^2)\).

Rerooting requires comfort with DP state transitions — understanding how the DP changes when the problem structure changes. It's covered in the DP Course after you've built intuition for state management on arrays and sequences. The tree structure from this course (postorder, subtree sizes, pair-return) is the foundation that rerooting builds on.

What's Next?

You now understand tree DP: subtree aggregation as DP states, and path DP with the arm-vs-bridge distinction. Chapter 10 shifts focus to how the explicit stack mirrors tree structure — a deeper understanding of iterative DFS that connects back to everything you learned in Chapter 2.