Mock 3 — Trees (60 min)

# Mock 3 — Trees ## The brief Four tree problems, 60 minutes. Trees test recursive thinking and traversal choice. ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right ``` ## Problem 1 — Maximum Depth (Easy, ~10 min) Find the maximum depth of a binary tree. ### Solution ```python def max_depth(root): if not root: return 0 return 1 + max(max_depth(root.left), max_depth(root.right)) ``` State the recurrence: depth = 1 + max(left depth, right depth). Base case: null is 0. ## Problem 2 — Lowest Common Ancestor (Medium, ~15 min) Given a tree and two nodes p and q, find their lowest common ancestor. ### Approach script 1. State: "Find lowest node that has both p and q as descendants." 2. Recursive insight: "If both found in left subtree, LCA is in left. Both in right, LCA in right. Split (one each side) → current node IS the LCA." 3. Base case: null returns null. If current matches p or q, return it. ### Solution ```python def lowest_common_ancestor(root, p, q): if not root or root == p or root == q: return root left = lowest_common_ancestor(root.left, p, q) right = lowest_common_ancestor(root.right, p, q) if left and right: # found p and q in different subtrees return root return left or right # both in same subtree ``` Elegant; understand WHY each line. ## Problem 3 — Diameter of Binary Tree (Medium, ~15 min) Find the length of the longest path between any two nodes (measured in edges). ### Approach script 1. State: "Longest path between any two nodes, by edge count." 2. Insight: "For each node, the longest path THROUGH it is leftHeight + rightHeight. Track global max." 3. Recurse to compute heights; update diameter at each node. ### Solution ```python def diameter_of_binary_tree(root): best = [0] def height(node): if not node: return 0 l = height(node.left) r = height(node.right) best[0] = max(best[0], l + r) # path through this node return 1 + max(l, r) height(root) return best[0] ``` Two outputs from one DFS: returns height upward; updates diameter globally. ## Problem 4 — Serialize and Deserialize (Hard, ~20 min) Design algorithms to serialize a binary tree to a string and deserialize back. ### Approach script 1. State: "Convert tree to string and back. Both must support any tree (including null branches)." 2. Pre-order with null markers: "Use pre-order DFS; mark nulls explicitly (`#`). To deserialize, consume tokens in pre-order, reconstructing tree." 3. Why pre-order? Because the order matches construction order. ### Solution ```python class Codec: def serialize(self, root): result = [] def dfs(node): if not node: result.append("#") return result.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ",".join(result) def deserialize(self, data): tokens = iter(data.split(",")) def build(): val = next(tokens) if val == "#": return None node = TreeNode(int(val)) node.left = build() node.right = build() return node return build() ``` The `iter` and `next` pattern makes the deserialize one-pass and clean. ## Self-rubric - [ ] All 4 solved correctly - [ ] LCA: understood why the "left and right both found" case returns current - [ ] Diameter: used global tracking (mutable container or class member) - [ ] Serialize: handled null markers explicitly - [ ] Could draw the recursion tree for at least one problem ## Deliverables - Solutions. - Diagram one of: LCA execution on a sample tree, OR serialize on a sample tree (showing the resulting string).