Advanced Tree Interview Patterns: Serialization, LCA, Path Problems, and BST Operations (2025)

By /
⏱ 6 min read

Tree Pattern Overview

Tree problems test recursive thinking and the ability to combine top-down and bottom-up information. Most tree problems reduce to one of: (1) traversal (pre/in/post-order), (2) a recursive function returning information up the tree (bottom-up), (3) passing information down into subtrees (top-down), or (4) combining both. The key skill is choosing the right return type for the recursive helper — sometimes you need to return multiple values (height + diameter, or sum + count).

Pattern 1: Serialize and Deserialize Binary Tree (LC 297)

BFS serialization: level-order traversal, using “null” for missing children. Clean, mirrors how the tree looks visually. DFS (preorder) serialization: root, left, right. Use a global index or deque to reconstruct in order. DFS approach is simpler to implement:

def serialize(root):
    vals = []
    def dfs(node):
        if not node: vals.append('#'); return
        vals.append(str(node.val))
        dfs(node.left); dfs(node.right)
    dfs(root)
    return ','.join(vals)

def deserialize(data):
    vals = iter(data.split(','))
    def dfs():
        v = next(vals)
        if v == '#': return None
        node = TreeNode(int(v))
        node.left = dfs()
        node.right = dfs()
        return node
    return dfs()

BST serialization shortcut: for BSTs only, in-order traversal produces a sorted array. Reconstruct the BST from the sorted array. But this doesn’t generalize to arbitrary binary trees — need both preorder + inorder (or the null-marker approach above).

Pattern 2: Lowest Common Ancestor (LC 236)

LCA of two nodes p and q: the deepest node that has both p and q in its subtree. Recursive approach: if root is null, p, or q: return root. Recurse left and right. If both return non-null: current node is the LCA. If only one returns non-null: return that value (either found p/q in that subtree, or already found LCA).

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:
        return root  # p is in one subtree, q in the other
    return left or right  # both in same subtree

For BST (LC 235): exploit BST property. If both p and q are less than root: LCA is in left subtree. If both greater: right subtree. Otherwise: root is LCA. O(h) time, O(1) space iteratively.

Pattern 3: Maximum Path Sum (LC 124)

A path in a binary tree is any sequence of nodes from some starting node to any ending node through parent-child connections. Find the path with the maximum sum. Key insight: the recursive helper returns the maximum gain starting from the current node going down one side (left or right). But during the recursion, also consider the path passing through the current node (left_gain + root.val + right_gain).

def max_path_sum(root):
    max_sum = [float('-inf')]
    def max_gain(node):
        if not node: return 0
        left = max(max_gain(node.left), 0)   # ignore negative paths
        right = max(max_gain(node.right), 0)
        max_sum[0] = max(max_sum[0], node.val + left + right)
        return node.val + max(left, right)  # can only go one way up
    max_gain(root)
    return max_sum[0]

The “max(gain, 0)” trick: if a subtree has a negative sum, ignore it entirely. This pattern (return one thing up, update global with another) appears in diameter of binary tree, longest zigzag path, and similar problems.

Pattern 4: BST Validation, Recovery, and Iterator

Validate BST (LC 98): pass valid range [lo, hi] top-down. For the left subtree, hi = current node value. For the right, lo = current node value. A common mistake: checking only parent-child relationships. Use the range approach. Recover BST (LC 99): two nodes are swapped by mistake. In-order traversal finds exactly two violations. Track first (where a node is larger than its successor) and second (where a node is smaller than its predecessor) violators. Swap their values. BST Iterator (LC 173): implement next() and hasNext() with O(h) memory (not O(n)). Use a stack: push all left children initially. On next(): pop from stack, push right child’s leftmost path. This simulates in-order traversal lazily. Kth Smallest in BST (LC 230): in-order traversal, count k nodes. Or augment the BST with subtree sizes for O(h) queries.

See also: Meta Interview Prep

See also: Atlassian Interview Prep

See also: Coinbase Interview Prep

Scroll to Top