Tree Interview Patterns
Trees appear in nearly every software engineering interview. Mastering the core traversal patterns and recognizing which technique applies is the key skill.
Pattern 1: DFS Traversals
Three orderings — preorder (root, left, right), inorder (left, root, right), postorder (left, right, root).
def inorder(root):
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)
# Iterative inorder (important for interviews):
def inorder_iter(root):
stack, result = [], []
cur = root
while cur or stack:
while cur:
stack.append(cur); cur = cur.left
cur = stack.pop()
result.append(cur.val)
cur = cur.right
return result
BST inorder produces a sorted sequence — used to validate BST, find kth smallest.
Pattern 2: BFS / Level Order
from collections import deque
def level_order(root):
if not root: return []
q, result = deque([root]), []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
result.append(level)
return result
Use BFS for: level-order traversal, min depth, zigzag traversal, connect next pointers.
Pattern 3: Tree DP (Bottom-Up)
Many tree problems require computing a value at each node based on its children. Classic: Diameter of Binary Tree.
def diameter(root):
best = [0]
def height(node):
if not node: return 0
L, R = height(node.left), height(node.right)
best[0] = max(best[0], L + R) # path through this node
return 1 + max(L, R)
height(root)
return best[0]
Pattern: return something to parent (height/gain/value), update a global answer at each node. Used for: diameter, max path sum, camera placement, rob houses on tree.
Pattern 4: Lowest Common Ancestor (LCA)
def lca(root, p, q):
if not root or root == p or root == q: return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right: return root # p and q on different sides
return left or right
For BST: if both p,q < root go left; if both > root go right; else root is LCA. O(log N) for balanced BST.
Pattern 5: BST Operations
- Search: O(h) — go left if val < root, right if val > root
- Insert: same as search until null, then create node
- Delete: (1) leaf: just remove; (2) one child: replace with child; (3) two children: replace with inorder successor (leftmost node in right subtree)
- Validate BST: pass min/max bounds down. At each node: val must be in (min, max). Left subtree max = current val; right subtree min = current val.
Pattern 6: Serialize / Deserialize
def serialize(root):
if not root: return 'N,'
return str(root.val) + ',' + serialize(root.left) + serialize(root.right)
def deserialize(data):
vals = iter(data.split(','))
def build():
v = next(vals)
if v == 'N': return None
node = TreeNode(int(v))
node.left, node.right = build(), build()
return node
return build()
Pattern 7: Path Problems
- Path sum: DFS with remaining target; return True when leaf reached with target=0
- All root-to-leaf paths: DFS with current path list; copy at leaf
- Max path sum: Tree DP — at each node, max gain from left/right subtrees (take max with 0 to skip negative branches)
Interview Tips
- Always handle the null base case first.
- Recursive DFS is clean for tree DP; iterative is needed if stack overflow is a concern (N=10^5).
- For BST problems, use the sorted inorder property as the primary insight.
- When the answer spans across two subtrees, track a global variable updated at each node.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the iterative inorder traversal algorithm and why is it important?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Iterative inorder uses an explicit stack to simulate the call stack of recursive DFS. Algorithm: maintain a current pointer starting at root and an empty stack. While current is not null or stack is not empty: (1) push current onto stack and go left (current = current.left) until current is null; (2) pop from stack, record the value; (3) move to the right child (current = popped.right). This produces left-root-right ordering. Why important: (1) avoids stack overflow for N=10^5 deep trees (skewed BST), (2) frequently asked in interviews alongside recursive version, (3) enables Morris traversal (O(1) space) as an extension. For BST, inorder visits nodes in sorted ascending order — used to find kth smallest, validate BST, merge two BSTs.” }
},
{
“@type”: “Question”,
“name”: “How do you find the Lowest Common Ancestor of two nodes in a binary tree?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “LCA in a binary tree (not BST): use recursive DFS. Base case: if root is null, return null; if root == p or root == q, return root. Recurse on both subtrees: left = lca(root.left, p, q); right = lca(root.right, p, q). If both left and right are non-null: p and q are in different subtrees, so root is the LCA. If only left is non-null: both nodes are in the left subtree, return left. If only right is non-null: return right. Time O(N), Space O(H). For BST: if both p and q are less than root, LCA is in left subtree; if both greater, right subtree; else root is the LCA — O(H) time and O(1) space iteratively. For LCA with parent pointers: traverse from each node to root collecting ancestors, find deepest common node using a set.” }
},
{
“@type”: “Question”,
“name”: “What is tree DP and how is it applied to the Diameter of Binary Tree problem?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Tree DP computes a value at each node using values from its children (bottom-up). For Diameter of Binary Tree: the diameter is the longest path between any two nodes — it may or may not pass through the root. At each node, the path through that node has length = height(left) + height(right). The global diameter is the maximum of this value across all nodes. Implementation: DFS function returns the height of the subtree rooted at the node. At each node, update global_max = max(global_max, left_height + right_height). Return 1 + max(left_height, right_height) to parent. This single DFS computes both the answer (via global variable) and the return value (height) the parent needs. The same pattern applies to: Binary Tree Maximum Path Sum (return max gain instead of height), House Robber on Trees (return rob/skip pair), and placing cameras on a tree (return coverage status).” }
}
]
}