The four tree traversals

Preorder, inorder, postorder and level order — and which question each one answers.

Lesson 47 of 75 · Beginner 2 min read

There are four standard ways to visit every node. The first three differ only in when you handle the current node relative to its children.

const preorder = (n, out = []) =>            // node, left, right
  n ? (out.push(n.value), preorder(n.left, out), preorder(n.right, out), out) : out;

const inorder = (n, out = []) =>             // left, node, right
  n ? (inorder(n.left, out), out.push(n.value), inorder(n.right, out), out) : out;

const postorder = (n, out = []) =>           // left, right, node
  n ? (postorder(n.left, out), postorder(n.right, out), out.push(n.value), out) : out;

Which one, and why

Traversal	Use it for
Preorder	Copying a tree, serialising it, exporting a directory listing — the parent must exist before its children
Inorder	Sorted output from a BST. Also validating a BST
Postorder	Deleting a tree, computing sizes or heights, evaluating an expression tree — children must finish first
Level order	Shortest path in an unweighted tree, printing by depth, "right side view"

Postorder is the one to reach for whenever a node's answer depends on its children's answers — which covers most "compute something about the tree" questions.

Level order, with a queue

function levelOrder(root) {
  if (!root) return [];

  const levels = [];
  const queue = [root];

  while (queue.length) {
    const size = queue.length;          // freeze the count: this is one level
    const level = [];

    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    levels.push(level);
  }

  return levels;
}

Capturing queue.length before the inner loop is what separates the levels. Without it you get a flat list — correct nodes, lost structure.

This is breadth-first search on a tree; the graphs chapter generalises it to arbitrary networks.

Cost

All four are O(n) time — every node once. Space differs: the depth-first three use O(h) stack, level order uses O(w) for the widest level, and for a balanced tree the bottom level holds half the nodes, so that is O(n).

For very deep trees, write the depth-first traversal iteratively with an explicit stack, as in chapter 6.