What does preorder traversal (prefix traversal) do?

AlgorithmsJunior~2 min read

Short answer

Preorder traversal (prefix traversal) visits a binary tree in the order: current node first (N), then the left subtree (L), then the right subtree (R), i.e., N-L-R. It visits the root before its descendants.

Detailed explanation

Preorder traversal defines the order in which the nodes of a binary tree are visited. At each step we first "process" the current node (for example, record its value), then recursively traverse the left subtree, then the right subtree.

Process the current node (visit it/add it to the result).
Recursively run preorder on the left subtree.
Recursively run preorder on the right subtree.

Time complexity: O(n), where n is the number of nodes (each node is visited exactly once).
Memory: O(h), where h is the tree's height (the depth of the call stack for recursion, or the size of the auxiliary stack for iteration). In the worst case (a degenerate tree) h = n.

Where preorder is used

Serializing/copying a tree (with explicit marking of null children).
Reconstructing a tree from preorder + inorder sequences.
Producing the prefix (Polish) notation of expressions in expression trees.

Example tree and traversal order

Preorder (N-L-R) for this tree: [1, 2, 4, 5, 3, 6].

Recursive implementation (JavaScript)

// Node definition
function TreeNode(val, left = null, right = null) {
  this.val = val;
  this.left = left;
  this.right = right;
}

// Preorder: N-L-R
function preorder(root) {
  const res = [];
  function dfs(node) {
    if (!node) return;
    res.push(node.val);      // N
    dfs(node.left);          // L
    dfs(node.right);         // R
  }
  dfs(root);
  return res;
}

// Example
const root = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(4),
    new TreeNode(5)
  ),
  new TreeNode(3,
    null,
    new TreeNode(6)
  )
);

console.log(preorder(root)); // [1, 2, 4, 5, 3, 6]

Iterative implementation (stack)

function preorderIterative(root) {
  if (!root) return [];
  const res = [];
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);           // visit the node
    if (node.right) stack.push(node.right); // push right first
    if (node.left) stack.push(node.left);   // then left, so left ends up on top of the stack
  }
  return res;
}

// Check
console.log(preorderIterative(root)); // [1, 2, 4, 5, 3, 6]

Differences from other traversals

Inorder (L-N-R): left, root, right. For a BST this produces a sorted sequence.
Postorder (L-R-N): left, right, root. Convenient for deleting/freeing resources bottom-up.
Preorder (N-L-R): root, left, right. Lets you "understand the structure first," then descend into subtrees.

Complexity and memory

Time: O(n), each node is visited once.
Memory: O(h) for the recursion/iteration stack; O(n) in the worst case (a linear tree).

Common mistakes and subtleties

Forgetting to process the current node before recursing (that would already be inorder/postorder).
Mixing up the push order in the iterative version: you must push the right child first, then the left.
Not accounting for null nodes during serialization (null must be explicitly recorded for unambiguous tree reconstruction).

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.