Trees & Traversal

Tree terminology

        1          ← root (depth 0)
       / \
      2   3        ← internal nodes (depth 1)
     / \   \
    4   5   6      ← leaves (depth 2)

• Root: top node, no parent
• Leaf: node with no children
• Depth of node: edges from root to node
• Height of tree: maximum depth of any leaf
• Binary tree: each node has at most 2 children (left and right)

class TreeNode {
  val:   number
  left:  TreeNode | null
  right: TreeNode | null
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val   = val
    this.left  = left
    this.right = right
  }
}

DFS: the three orderings

Depth-First Search visits nodes deep before wide. The three orderings differ only in when you process the current node relative to its children.

Inorder: left → root → right

function inorder(root: TreeNode | null): number[] {
  if (root === null) return []
  return [
    ...inorder(root.left),
    root.val,
    ...inorder(root.right),
  ]
}

Inorder traversal of a Binary Search Tree yields elements in sorted order. This is the main reason inorder exists — it’s the BST-specific traversal.

Preorder: root → left → right

function preorder(root: TreeNode | null): number[] {
  if (root === null) return []
  return [
    root.val,
    ...preorder(root.left),
    ...preorder(root.right),
  ]
}

Visit root before children. Use cases: serializing a tree, copying a tree, printing directory structure.

Postorder: left → right → root

function postorder(root: TreeNode | null): number[] {
  if (root === null) return []
  return [
    ...postorder(root.left),
    ...postorder(root.right),
    root.val,
  ]
}

Visit children before root. Use cases: deleting a tree (delete children before parent), computing subtree values (calculate children first, then combine at parent).

Iterative DFS (using a stack)

Recursion uses the call stack implicitly. You can make it explicit with your own stack — required when the tree is deep enough to cause stack overflow.

function preorderIterative(root: TreeNode | null): number[] {
  if (!root) return []
  const result: number[] = []
  const stack: TreeNode[] = [root]
  while (stack.length > 0) {
    const node = stack.pop()!
    result.push(node.val)
    if (node.right) stack.push(node.right)  // right first (LIFO → left processed first)
    if (node.left)  stack.push(node.left)
  }
  return result
}

BFS: level-order traversal

Breadth-First Search visits nodes level by level. Uses a queue.

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return []
  const result: number[][] = []
  const queue: TreeNode[]  = [root]

  while (queue.length > 0) {
    const levelSize = queue.length  // number of nodes at current level
    const level: number[] = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!
      level.push(node.val)
      if (node.left)  queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    result.push(level)
  }
  return result
}

The levelSize snapshot is the key — it tells you how many nodes are in the current level before you start adding the next level.

DFS vs BFS: when to use which

BFS uses O(w) queue space where w is the maximum width. DFS uses O(h) stack space where h is height. For a balanced tree, h ≈ log n. For a skewed tree (worst case), h = n.

Classic problems

Maximum depth

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
}

Same tree

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true
  if (!p || !q) return false
  return p.val === q.val
    && isSameTree(p.left, q.left)
    && isSameTree(p.right, q.right)
}

Path sum

Does a root-to-leaf path with sum target exist?

function hasPathSum(root: TreeNode | null, target: number): boolean {
  if (!root) return false
  if (!root.left && !root.right) return root.val === target  // leaf
  return hasPathSum(root.left,  target - root.val)
      || hasPathSum(root.right, target - root.val)
}

Mirror / symmetric tree

function isSymmetric(root: TreeNode | null): boolean {
  function mirror(a: TreeNode | null, b: TreeNode | null): boolean {
    if (!a && !b) return true
    if (!a || !b) return false
    return a.val === b.val
      && mirror(a.left,  b.right)
      && mirror(a.right, b.left)
  }
  return !root || mirror(root.left, root.right)
}

The recursive tree template

Most tree problems fit this shape:

function solve(node: TreeNode | null): SomeType {
  // Base case: null node
  if (!node) return baseValue

  // Recurse into children
  const left  = solve(node.left)
  const right = solve(node.right)

  // Combine results (postorder style)
  return combineWith(node.val, left, right)
}

Internalize this template. When you see a tree problem, your first question is: “what should this function return for each node, and how do I combine child results at the parent?”

Complexity

Where n = total nodes, h = height, w = max width. For a balanced binary tree: h = O(log n), w = O(n/2) = O(n) at the last level.