Interview OS
Back to Coding Prep

Coding

Trees

Recursion on left/right subtrees; DFS / BFS traversals.

Coding pattern

Overview

Tree problems ask you to combine answers from sub-structures. You pick a traversal (DFS pre/in/post-order or BFS level-order), compute per-node results, and merge child answers upward — the mental model behind depths, paths, and ancestor queries.

How it works

Coding pattern
InputTraverseCombineOutputRoot nodebinary/n-aryDFS / BFSrecursion/queueMerge resultsleft+rightAnswer
ClientServiceEdgeData

Step by step, with examples

  1. 1

    Root node

    • Start at the root; know the tree's shape.
  2. 2

    DFS / BFS

    • Recurse pre/in/post-order or go level-order.
  3. 3

    Merge results

    • Aggregate child answers back up the tree.
  4. 4

    Answer

    • Return a height, path, or node value.
    • Example: Max depth, LCA

When to reach for it

  • Hierarchical data
  • Depth / height questions
  • BST ordering

Example problem

Maximum depth of a binary tree.

Approach

  • Recurse on both children
  • Depth = 1 + max(left, right)

Solution

function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Complexity

Time O(n), Space O(h) for recursion.

Common pitfalls

  • Missing the null base case
  • Stack overflow on skewed trees

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions