Tree DP

Opening scenario

Problem references use LC for LeetCode.

In a non-empty binary tree, a path is a non-empty sequence of distinct nodes connected by edges. It need not pass through the root. Relative to the root, it can go upward to one highest node and then downward; this is the "bend" discussed below. Return the maximum sum of node values along any path (LC 124, Binary Tree Maximum Path Sum). The interviewer stays on trees. House Robber on a tree: pick nodes for the largest total value, but never a node and its child together. Tree cameras: place the fewest cameras so every node is covered, where one camera covers its own node, its parent and its children. Each problem needs a summary of a subtree that its parent can use; some summaries have several states, while others use one returned value plus a separately recorded answer.

The examples use nodes with val, left, and right fields. The distance example instead takes n ≥ 1 nodes labeled 0..n-1 and undirected edges forming a connected tree, with each edge having length 1. Start by asking which part of a child’s solution the parent can legally extend.