Tree algorithms interview questions

The tree-recursion template (memorize this once)

Most tree problems fit one pattern. Learn this template once; reuse forever.

function solve(node):
  if node is None:
    return base_case

  left_result = solve(node.left)
  right_result = solve(node.right)

  # combine left, right, and node.val
  return combined_result

Almost every tree problem boils down to: define base_case, define how left_result and right_result combine with node.val. Diameter, depth, balanced-check, path-sum, lowest-common-ancestor — all variations of this template.

• Variation 1: Return multiple values. Some problems need both an answer AND a state (e.g., is-balanced + height). Return a tuple.
• Variation 2: Use a class-level result. For problems like “diameter”, you update a global max while recursing.
• Variation 3: Pass state down. Some problems pass cumulative state (e.g., path-sum) as a parameter.

The 8 most common tree interview questions

1. Maximum depth of binary tree — Basic recursion template warm-up
2. Validate binary search tree — In-order traversal yields sorted; equivalently pass min/max bounds
3. Lowest common ancestor (LCA) — Two variants: BST and general binary tree
4. Serialize and deserialize binary tree — Pre-order with null markers
5. Diameter of binary tree — DP-on-trees with global max
6. Path sum (II — return all paths) — DFS with backtracking
7. Construct binary tree from preorder + inorder — Recursion with hashmap for O(n)
8. Binary tree right side view — Level-order BFS, take last per level

Tries — when the cleanest solution is a tree of characters

Trie problems are usually disguised as string-search problems. Recognition cue: ‘starts with’, ‘prefix’, ‘autocomplete’, ‘word search in a board’.

• Implement Trie (insert, search, startsWith). Canonical problem.
• Word search II. Trie + DFS on the board. Brute-force is too slow.
• Replace words. Trie of dictionary roots; walk each input word until you hit a root.
• Longest word in dictionary. Trie + BFS or DFS, taking longest path with all prefixes present.

Frequently asked questions

Explore related tools