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).
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the “gain vs answer” duality in tree DP problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Many tree DP problems have two quantities: (1) the answer to the global problem (e.g., maximum path sum across the entire tree) and (2) what a subtree can contribute to its parent (e.g., the max gain of a path starting at this node going downward). The helper function returns the “contribution” value, while updating the global answer as a side effect. This pattern appears in: maximum path sum (contribution = node.val + max(left, right); answer updated with node.val + left + right), tree diameter (contribution = 1 + max(left_depth, right_depth); answer updated with left_depth + right_depth), and longest path with specific properties. The key insight: the contribution to the parent is constrained (a path through the parent can only come from one child), while the local answer uses both children. Always separate these two.”
}
},
{
“@type”: “Question”,
“name”: “How does the Lowest Common Ancestor algorithm work and what are its variants?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Basic LCA (LC 236): recursively search both subtrees. If current node is p or q: return it. Recurse left and right. If both return non-null: current node is the LCA (p and q are in different subtrees). If one returns null: LCA is in the non-null subtree. Return the non-null result upward. O(n) time, O(h) space. LCA with parent pointers: collect ancestors of p in a set (traverse via parent pointers to root). Traverse from q upward; first node found in the set is the LCA. O(h) time. For repeated LCA queries on the same tree: binary lifting (O(n log n) preprocessing, O(log n) per query) or Euler tour + RMQ (range minimum query, O(n) preprocessing, O(1) per query). Binary lifting precomputes 2^k-th ancestor for each node; LCA = the highest common ancestor found by doubling jumps.”
}
},
{
“@type”: “Question”,
“name”: “How do you serialize and deserialize a binary tree uniquely?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “A preorder traversal alone does not uniquely identify a tree (different trees can have the same preorder). To serialize uniquely with preorder: include null markers (e.g., “#”) for missing children. “1,2,#,#,3,4,#,#,5,#,#” uniquely represents a specific tree. Deserialization: use a queue of tokens. pop_front() = root value. If “#”: return null. Otherwise: root = TreeNode(val); root.left = deserialize(queue); root.right = deserialize(queue). The key insight: preorder + null markers tells you the exact structure because every absent child is explicitly marked, giving the deserializer enough information to reconstruct without ambiguity. Inorder alone is NOT sufficient even with null markers (left-skewed vs right-skewed look different in preorder). Inorder + preorder together suffice for trees without duplicate values.”
}
},
{
“@type”: “Question”,
“name”: “What is the approach for binary tree path problems that involve sums?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Three variants: (1) Path from root to leaf with target sum (LC 112/113): maintain a running sum as you DFS downward. At a leaf: check if running_sum == target. For all paths (LC 113): backtrack (undo the addition after recursing). (2) Path between any two nodes (LC 124 maximum path sum, LC 687 longest univalue path): use the tree DP pattern — at each node, compute the best path through this node using both subtrees, update global answer, return the best one-directional path for the parent. (3) Path count with target sum in subtree (LC 437): prefix sum approach. Maintain a dictionary of prefix sums seen on the current root-to-node path. At each node: check if (current_prefix_sum – target) is in the dict. This is O(n) vs O(n^2) for the naive approach of trying all pairs of ancestors.”
}
},
{
“@type”: “Question”,
“name”: “How do you solve the tree diameter problem for weighted trees?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Unweighted diameter (LC 543): at each node, diameter_through_node = left_depth + right_depth. Return max(left_depth, right_depth) + 1 to parent. Weighted diameter: replace depth with the sum of edge weights. The longest path between any two nodes. Same DFS approach: maintain a global max. At each node: compute left_gain = max(0, weighted_dfs(left)) and right_gain = max(0, weighted_dfs(right)). Update max_diameter = max(max_diameter, left_gain + right_gain). Return max(left_gain, right_gain) + edge_weight to parent. The algorithm structure is identical — only the accumulation changes from +1 per node to +edge_weight per edge. For the diameter of a general (non-binary) tree: at each node, the diameter through it = sum of the two largest child gains. Sort child gains descending; take the top two. Return the largest to the parent.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide