Binary Tree Practice Problems

How to Use This Problem List

Binary tree problems look diverse but follow a small number of structural patterns. The key skill is recognising which of four thinking modes a problem belongs to:

MODE 1 — TOP-DOWN (Preorder thinking):
  Pass information from parent to children.
  Decision at each node uses data from ancestors.
  Example: check if path sum equals target

MODE 2 — BOTTOM-UP (Postorder thinking):
  Collect information from children to compute parent.
  Decision at each node uses results from descendants.
  Example: height, diameter, balanced check

MODE 3 — LEVEL AWARENESS (BFS thinking):
  Need to process or compare nodes at the same depth.
  Example: right side view, zigzag traversal, max width

MODE 4 — STRUCTURAL (Inorder thinking):
  BST-specific — inorder gives sorted order.
  Example: validate BST, kth smallest

Identify the mode before writing code. The implementation follows mechanically from the correct mode.

Pattern 1: Tree Metrics — Height, Size, Depth

Properties of the tree that require visiting every node once. All are O(n) time with O(h) space.

Complexity target: O(n) time, O(h) space. O(log² n) time for Complete Tree Nodes.

Recognition signal: "depth", "height", "count", "sum of all", "width", "level". A single numeric property of the entire tree or each level.

Pattern 2: Path Problems

A path is a sequence of nodes from some starting node downward or between any two nodes. Always think about what information flows along the path.

Complexity target: O(n) time, O(h) space for stack/recursion.

Recognition signal: "root-to-leaf", "path sum", "any path", "digits along path". Something accumulates as you travel from node to node.

Pattern 3: Tree Structure — Shape, Symmetry, Balance

Problems about the structural shape of the tree independent of values.

Complexity target: O(n) time, O(h) space. Subtree check is O(S×T) naive or O(S+T) with hashing.

Recognition signal: "symmetric", "same", "balanced", "flip", "subtree", "complete", "invert". The problem asks about the tree's shape or structural relationship.

Pattern 4: Tree Construction and Transformation

Build a tree from given data, or transform an existing tree into a different form.

Complexity target: O(n) time, O(n) space (for output or reconstruction).

Recognition signal: "construct", "build", "flatten", "serialize", "convert". The problem creates a new tree or restructures an existing one.

Pattern 5: Lowest Common Ancestor (LCA) and Ancestors

Problems involving ancestors, paths between nodes, and finding common nodes.

Complexity target: O(n) time O(n) space preprocessing; O(log n) per query with binary lifting.

Recognition signal: "common ancestor", "path between nodes", "distance from", "k edges away". The problem requires tracing paths upward or between nodes.

Pattern 6: Level-Based Problems (BFS)

Problems where the answer depends on which level a node is on, or requires processing nodes in level order.

Complexity target: O(n) time, O(w) space where w = max level width.

Recognition signal: "level", "each row", "level by level", "depth k", "rightmost/leftmost at depth". Anything about nodes at the same horizontal position.

Recommended Study Order

Week 1 — Foundations
  Pattern 1 (Metrics):   Max Depth, Min Depth, Count Nodes
  Pattern 3 (Structure): Symmetric Tree, Same Tree, Invert Binary Tree

Week 2 — Core DFS Patterns
  Pattern 2 (Paths):     Path Sum, Binary Tree Paths, Path Sum II
  Pattern 3 (Structure): Balanced Binary Tree, Diameter of Binary Tree

Week 3 — Intermediate
  Pattern 5 (Ancestors): LCA of Binary Tree, LCA of BST
  Pattern 4 (Build):     Construct from Preorder+Inorder, Flatten Tree
  Pattern 6 (BFS):       Level Order, Zigzag, Right Side View

Week 4 — Hard Problems
  Pattern 2 (Paths):     Binary Tree Maximum Path Sum, Path Sum III
  Pattern 4 (Build):     Serialize and Deserialize Binary Tree
  Pattern 5 (Ancestors): All Nodes at Distance K, Distance Between Two Nodes
  Revisit any pattern that felt unclear

Problem-Solving Checklist for Binary Tree Problems

Before writing code, answer these questions:

1. IDENTIFY THE THINKING MODE
   □ Top-down (preorder): does each node need info from its parent?
   □ Bottom-up (postorder): does each node need results from children?
   □ Level-based (BFS): does position (level/column) matter?
   □ Structural (inorder + BST): does order of values matter?

2. DEFINE WHAT THE RECURSIVE FUNCTION RETURNS
   □ A single value (height, count, sum)?
   □ A boolean (is balanced, are same)?
   □ A node (LCA, first occurrence)?
   □ Multiple values (use a global variable or tuple/pair return)?

3. WRITE THE BASE CASES FIRST
   □ null node — what to return? (0 for height, true for symmetry, null for LCA)
   □ leaf node — any special case beyond null?

4. WRITE THE RECURSIVE CASE
   □ What does left subtree contribute?
   □ What does right subtree contribute?
   □ How are they combined at the current node?

5. CHECK FOR GLOBAL STATE
   □ Does the answer require updating a variable across all nodes?
     (diameter, max path sum, count of nodes)
   □ If yes: use a class-level variable or a single-element array/list

6. EDGE CASES
   □ Empty tree (null root)
   □ Single node tree (root only, no children)
   □ All nodes on one side (skewed tree)
   □ Negative values (for path sum problems)

Pattern Recognition Quick Reference

Difficulty Progression Reference

Common Interview Topics by Company Focus

Product-based companies (FAANG-tier):

• ›Binary Tree Maximum Path Sum — the canonical hard tree problem
• ›Serialize and Deserialize Binary Tree — design + recursion
• ›Construct Binary Tree from Preorder + Inorder — fundamental construction
• ›Diameter of Binary Tree — postorder global max pattern
• ›LCA of Binary Tree — ancestor traversal
• ›All Nodes at Distance K — multi-technique combination
• ›Symmetric Tree — pairwise structural comparison

Service-based and on-campus:

• ›Max Depth, Min Depth, Invert Tree — postorder basics
• ›Level Order, Right Side View — BFS patterns
• ›Path Sum, Path Sum II — path accumulation
• ›Same Tree, Subtree of Another Tree — structural comparison

Startup and mid-size tech:

• ›Flatten Binary Tree to Linked List — in-place transformation
• ›Populating Next Right Pointers — O(1) space BFS
• ›Count Good Nodes — top-down with running max
• ›Binary Tree Paths — backtracking with string path

Progress Tracking

After solving each problem, record:

1. ›Thinking mode — top-down, bottom-up, BFS, or inorder?
2. ›What the recursive function returned — value, boolean, node, or tuple?
3. ›Base cases used — null → ? and leaf → ?
4. ›Global variable needed? — and what did it track?
5. ›Edge cases caught or missed — null root? Single node? Negative values?
6. ›Time to solve — target 15-20 minutes for easy, 25-30 for medium under interview conditions

The decisive signal that pattern recognition is working: when you see "diameter of binary tree" and immediately think "postorder — at each node, left_height + right_height updates global max, return 1 + max(left, right) to parent" — before reading the constraints or examples.