Tree DP

DP on trees: diameter, max path sum, house robber III.

7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Tree DP Concept

DP on trees: for each node, compute answer using children's results. Typically post-order traversal (process children before parent). Return value(s) to parent. Two patterns: (1) single value returned, (2) pair of values (e.g., take/skip).

Tree Diameter

Longest path between any two nodes. For each node, compute longest path through it = max depth of left + max depth of right. Track global max.

Gotree-diameter.go

18 linesLn 1, Col 1Go

dfs returns height of subtree. At each node, path through it = left height + right height. Update global ans. Return height = 1 + max(left, right).

Max Path Sum

Path can start/end at any nodes, must be connected. For each node, compute max path sum starting at node and going down. Also track max path through node (left + node + right).

Gomax-path-sum.go

20 linesLn 1, Col 1Go

Max path can be: node alone, node+left, node+right, or left+node+right. Return max downward path to parent. Ignore negative sums (treat as 0).

House Robber III

Binary tree, can't rob adjacent nodes. For each node, return pair: (rob this node, skip this node). If rob: node.Val + skip(left) + skip(right). If skip: max(rob, skip) for both children.

Gohouse-robber-iii.go

15 linesLn 1, Col 1Go

Post-order returns (rob, skip). If rob current: add value + skip children. If skip: take max of rob/skip for each child independently.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.