Tree traversals

Overview

A traversal visits every node of a tree exactly once in a specific order. Depth-first traversals go deep before wide: preorder (node, left, right), inorder (left, node, right), and postorder (left, right, node). Breadth-first (level order) visits nodes level by level with a queue.

The order is not a detail: it determines what the algorithm can do. Inorder on a BST gives sorted values. Preorder copies or serializes a tree. Postorder computes subtree results before the parent (deleting a tree, sizes, heights). Level order finds the shallowest nodes and per-level answers.

When to use it

• Preorder: copy, serialize, or print the tree structure; pass information from root to leaves.
• Inorder: process a BST in sorted order; validate BSTs; kth smallest.
• Postorder: compute values that depend on children first; free memory; evaluate expression trees.
• Level order: per-level answers, right side view, minimum depth, shortest distance.

Problem patterns it solves

Where it is used in real software

Key terms

Preorder

Node, left, right.

Inorder

Left, node, right.

Postorder

Left, right, node.

Level order

Level by level, left to right, using a queue.

Morris traversal

Inorder in O(1) space by temporarily threading right pointers.

Iterative inorder with an explicit stack

1. 1
   Go left as far as possible

   Push each node while moving to node.left.

2. 2
   Pop and visit

   The popped node has no unvisited left subtree, so visit it.

3. 3
   Move to the right child

   Repeat the process on the right subtree.

4. 4
   Stop

   When the current node is null and the stack is empty.

All four orders on one tree

Tree: 4 is the root; 2 (children 1, 3) on the left; 6 (children 5, 7) on the right. This is a BST.

Inorder printed the BST in sorted order. Preorder starts with the root, and postorder ends with it, which is why either one plus inorder is enough to rebuild the tree.

Implementation

1function preorder(root, out = []) {2  if (!root) return out;3  out.push(root.val);4  preorder(root.left, out);5  preorder(root.right, out);6  return out;7}8 9function inorderIterative(root) {10  const out = [], stack = [];11  let node = root;12  while (node || stack.length) {13    while (node) {14      stack.push(node);15      node = node.left;16    }17    node = stack.pop();18    out.push(node.val);19    node = node.right;20  }21  return out;22}23 24// Postorder iteratively: reverse of (node, right, left)25function postorderIterative(root) {26  if (!root) return [];27  const out = [], stack = [root];28  while (stack.length) {29    const node = stack.pop();30    out.push(node.val);31    if (node.left) stack.push(node.left);32    if (node.right) stack.push(node.right);33  }34  return out.reverse();35}36 37function rightSideView(root) {38  if (!root) return [];39  const result = [];40  let level = [root];41  while (level.length) {42    result.push(level.at(-1).val);43    const next = [];44    for (const node of level) {45      if (node.left) next.push(node.left);46      if (node.right) next.push(node.right);47    }48    level = next;49  }50  return result;51}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Iterative preorder pushing left before right.

  Fix: Push right first so left is popped first.

• Reading queue length inside the level loop.

  Fix: Capture the level size before processing the level.

• Rebuilding from preorder and postorder only.

  Fix: Without inorder, the tree is not unique unless it is full.

Interview questions

Practice problems