Preorder Tree Traversal Tutorial | Learn Data Structures

What Is Preorder Traversal?

Preorder traversal is a depth-first tree traversal technique in which the current node is processed before its left and right subtrees.

Root → Left → Right

The name "preorder" comes from the position of the root node. The root is processed before its child subtrees are traversed.

Preorder traversal is useful when the parent node must be handled before its descendants. It is commonly used for copying tree structures, generating prefix expressions, and solving binary tree problems.

Example Binary Tree

Consider the following binary tree:

          50
         /  \
       30    70
      /  \  /  \
    20   40 60   80

Starting at the root, preorder traversal processes 50 first. It then traverses the entire left subtree before moving to the right subtree.

Preorder:

50 → 30 → 20 → 40 → 70 → 60 → 80

How Preorder Traversal Works

For every node, preorder traversal follows three steps:

Process the current node.
Traverse the left subtree.
Traverse the right subtree.

These steps are repeated for each subtree until every reachable node has been visited.

Tracing Preorder Traversal

Start with the root node:

          50
         /  \
       30    70
      /  \  /  \
    20   40 60   80

The first node processed is 50 because preorder always processes the root before its children.

The traversal then enters the left subtree rooted at 30. Node 30 is processed before either of its children.

50 → 30

Node 20 is then processed, followed by node 40.

50 → 30 → 20 → 40

After completing the left subtree, traversal moves to the right subtree rooted at 70. Node 70 is processed before 60 and 80.

50 → 30 → 20 → 40 → 70 → 60 → 80

Recursive Preorder Traversal

Recursive implementation closely follows the definition of preorder traversal. The current node is added to the result before the recursive calls for its children.

function preorder(root, result = []) {
  if (root === null) {
    return result;
  }

  result.push(root.value);
  preorder(root.left, result);
  preorder(root.right, result);

  return result;
}

The position of result.push(root.value) is important. Moving it after the recursive calls would change the traversal order.

Complete Recursive Example

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function preorder(root, result = []) {
  if (root === null) {
    return result;
  }

  result.push(root.value);
  preorder(root.left, result);
  preorder(root.right, result);

  return result;
}

const root = new Node(50);

root.left = new Node(30);
root.right = new Node(70);

root.left.left = new Node(20);
root.left.right = new Node(40);

root.right.left = new Node(60);
root.right.right = new Node(80);

console.log(preorder(root));

Why the Root Comes First

Preorder traversal is defined by processing the current node before either subtree. This makes it different from inorder and postorder traversal.

Traversal	Order	Root Position
Preorder	Root → Left → Right	First
Inorder	Left → Root → Right	Middle
Postorder	Left → Right → Root	Last

Iterative Preorder Traversal

Preorder traversal can be implemented iteratively using a stack. The stack replaces the recursive call stack used by the recursive solution.

function preorderIterative(root) {
  if (root === null) {
    return [];
  }

  const stack = [root];
  const result = [];

  while (stack.length > 0) {
    const node = stack.pop();

    result.push(node.value);

    if (node.right !== null) {
      stack.push(node.right);
    }

    if (node.left !== null) {
      stack.push(node.left);
    }
  }

  return result;
}

Why Is the Right Child Pushed First?

A stack follows the Last-In, First-Out principle. Preorder requires the left child to be processed before the right child, so the right child must be pushed onto the stack first.

Push right
Push left

Stack top
   ↓
  left
  right

The left child is therefore removed from the stack before the right child.

Recursive vs Iterative Preorder Traversal

Aspect	Recursive	Iterative
Main technique	Function call stack	Explicit stack
Implementation	Short and direct	More explicit control
Time	O(n)	O(n)
Auxiliary space	O(h)	O(h)

Preorder Traversal and Tree Structure

Preorder traversal is useful when the parent-child relationship needs to be processed from the top of the tree downward. Since each parent appears before its descendants, the result naturally follows the hierarchical structure of the tree.

For example:

Preorder produces:

A → B → D → E → C

Notice that A appears before B and C, while B appears before D and E.

Using Preorder to Copy a Tree

Preorder traversal can be useful when creating a copy or serialized representation of a tree because each parent can be processed before its children.

A preorder sequence by itself does not always uniquely describe an arbitrary binary tree. Additional information, such as null-child markers or another traversal sequence, may be required to reconstruct the original structure.

Preorder Traversal for Expression Trees

Expression trees can represent operators and operands as nodes. Preorder traversal visits an operator before its operands, which corresponds naturally to prefix notation.

Preorder traversal produces:

+ → 5 → * → 2 → 3

This can be interpreted as the prefix expression:

+ 5 * 2 3

Preorder Traversal in Binary Search Trees

Preorder traversal of a Binary Search Tree does not produce sorted values. Instead, it records each parent before its descendants.

BST:

        50
       /  \
     30    70
    /  \  /  \
  20   40 60   80

Preorder:

50, 30, 20, 40, 70, 60, 80

This distinction is important when choosing a traversal. Inorder is commonly associated with sorted BST output, while preorder preserves a parent-before-children processing order.

Preorder Traversal Complexity

A complete preorder traversal visits every node exactly once. Therefore, its time complexity is O(n), where n is the number of nodes.

Implementation	Time	Auxiliary Space
Recursive	O(n)	O(h)
Iterative	O(n)	O(h)

Here, h represents the height of the tree. In a balanced tree, the height is typically O(log n), while a completely skewed tree can have height O(n).

Where Preorder Traversal Is Used

Preorder traversal is useful whenever a parent or root should be processed before its descendants.

Copying or serializing tree structures
Generating prefix expressions from expression trees
Processing hierarchical data from parent to child
Building tree representations
Binary tree interview and coding problems
Traversing directory-like hierarchical structures
Processing nodes before their dependent child nodes

Common Preorder Traversal Mistakes

Confusing preorder with inorder traversal.
Processing the root after traversing the left subtree.
Forgetting to process the current node before recursive calls.
Forgetting the null-node base case.
Pushing the left child before the right child in the iterative implementation.
Assuming preorder traversal produces sorted values for a BST.
Ignoring the difference between traversal order and tree structure.

Preorder vs Inorder vs Postorder

The easiest way to distinguish the three depth-first traversals is to look at where the root is processed.

Traversal	Pattern	Root Position	Typical Use
Preorder	Root → Left → Right	First	Parent-before-child processing
Inorder	Left → Root → Right	Middle	Sorted BST traversal
Postorder	Left → Right → Root	Last	Child-before-parent processing

Key Takeaways

Preorder traversal follows Root → Left → Right.
The current node is processed before either child subtree.
Preorder is a depth-first traversal technique.
Recursive preorder traversal naturally follows the definition of the algorithm.
An iterative implementation uses a stack.
The right child is pushed before the left child when using a stack.
Preorder traversal does not produce sorted output from a BST.
It is useful for parent-before-child processing and tree representation tasks.
A complete preorder traversal takes O(n) time.
Auxiliary traversal space is O(h), where h is the tree height.

Topics

Preorder Tree Traversal