Tree DP Pattern
Many tree problems require computing an answer that depends on both subtrees. The key pattern: define a helper function that returns information about a subtree (not just the final answer). The helper returns what the parent needs to continue the computation. Global result is updated inside the helper as a side effect. This “contribute to parent vs contribute to answer” duality is the core of tree DP.
Binary Tree Maximum Path Sum (LC 124)
A path can go through any node and can start and end at any node. The path may not pass through the root. Define gain(node): the maximum contribution this subtree can make to a path passing through its parent (must continue in one direction). gain(null) = 0. At each node: left = max(gain(node.left), 0) (ignore negative contributions). right = max(gain(node.right), 0). Update global max: max_sum = max(max_sum, node.val + left + right) (path through this node uses both children). Return to parent: node.val + max(left, right) (can only extend in one direction). O(n) time.
def maxPathSum(root):
max_sum = [float('-inf')]
def gain(node):
if not node: return 0
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
max_sum[0] = max(max_sum[0], node.val + left + right)
return node.val + max(left, right)
gain(root)
return max_sum[0]Diameter of Binary Tree (LC 543)
Diameter = longest path between any two nodes (number of edges). Same pattern: at each node, diameter through this node = left_depth + right_depth. depth(node) = 1 + max(depth(left), depth(right)). Update global diameter = max(diameter, left_depth + right_depth). O(n) time.
Lowest Common Ancestor (LC 236)
LCA of two nodes p and q is the deepest node that is an ancestor of both. Recursive approach: if node is null, p, or q: return node. Recurse both subtrees: left = lca(node.left), right = lca(node.right). If both return non-null: node is the LCA (p and q are in different subtrees). If only one returns non-null: return that (both p and q are in that subtree). O(n) time, O(h) space for recursion stack. LCA with parent pointers: traverse from p to root, store the path in a set. Traverse from q to root; first node in the set is the LCA. O(h) time and space.
Tree Serialization and Deserialization (LC 297)
Serialize: preorder traversal, represent null nodes with “#”. “1,2,#,#,3,4,#,#,5,#,#”. Deserialize: parse the string; use a queue or index pointer; preorder reconstruction: root = next value; if not “#”: root.left = deserialize(); root.right = deserialize(). This works because preorder uniquely identifies the tree structure when null nodes are recorded. Alternative: level-order (BFS) serialization — output nodes level by level, use “null” for absent children. Both are O(n). LeetCode 449 uses preorder of a BST with no null markers (BST property allows reconstruction without null records).
Vertical Order Traversal (LC 987)
Each node has a column index: root=0, left child=col-1, right child=col+1. A row index: root=0, children=row+1. Collect (col, row, val) for each node via BFS or DFS. Sort by (col, row, val). Group by col. This problem is a clean combination of tree traversal + sorting. Key: use BFS with a queue of (node, col, row) to avoid the complexity of managing global state in DFS.
Flatten Binary Tree to Linked List (LC 114)
Flatten in-place to a preorder linked list using the right pointer. Approach: for each node, if it has a left child: find the rightmost node of the left subtree. Connect that rightmost node’s right pointer to node.right. Move the left subtree to the right. Set left to null. Move to node.right. O(n) time, O(1) extra space (no recursion stack).
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide