Tree Traversal

Pre-order

What is Pre-order Traversal?

Pre-order traversal visits a node before either of its subtrees — the order is Root, then Left, then Right. It's called "pre" because the root is processed pre-emptively, ahead of anything below it, which makes it the natural way to reconstruct a tree's structure from scratch: whatever value you see first is guaranteed to be some subtree's root.

How Does It Work?

  1. Visit the root first: 8
  2. Recurse into the left subtree, visiting its root first: 3
  3. Recurse further left: 1 (a leaf, so no children to descend into)
  4. Back up to 3, now recurse right: 6
  5. All of 8's left subtree is done — recurse into 8's right subtree: 10
  6. Final sequence: [8, 3, 1, 6, 10]
81321364105
Visit orderNode

Because the root is always recorded before its children, pre-order output preserves enough structural information to rebuild the exact same tree (given the traversal is unambiguous, e.g. paired with node count or null markers). This is exactly why pre-order is the traversal used for serializing a tree to a file and for copying/cloning a tree — you can reconstruct it top-down as you read the sequence.

Pre-order also mirrors how you'd write a prefix (Polish notation) expression from an expression tree: the operator (root) comes before its operands (children), e.g. `+ 3 4` instead of `3 + 4`.

Algorithm Steps

  1. If the current node is null, return immediately (base case)
  2. Visit (process) the current node
  3. Recursively traverse the left subtree
  4. Recursively traverse the right subtree

Time Complexity

  • Time Complexity: Every node is visited exactly once → O(n).
  • Space Complexity: Bounded by the recursion depth → O(h).

Time Complexity Analysis

Advertisement

Traversal needs O(h) extra space for the recursion call stack, where h is the tree's height — O(log n) for a balanced tree, but O(n) in the worst case of a completely skewed tree.

Daily DSA Challenge by Scale Engineer

Build a tree, then watch pre-order visit Root → Left → Right

Tree is empty
No tree yet — insert a value or generate a random tree
Not yet visitedVisitedCurrently visitingRoot

Test Your Knowledge before moving forward!

Pre-order Traversal Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Pre-order Traversal Implementation

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Pre-order traversal: Root -> Left -> Right
function preOrder(node, result = []) {
  if (node === null) return result;

  result.push(node.value); // visit root first
  preOrder(node.left, result);
  preOrder(node.right, result);

  return result;
}

// Usage example
let root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);

console.log(preOrder(root)); // [8, 3, 1, 6, 10]

Done With the Learning

Mark Pre-order Traversal as done and view it on your dashboard

Explore Other Tree Topics

In-order Traversal

Post-order Traversal

Level-order Traversal

Morris Traversal

BST Insertion

BST Deletion

BST Searching

AVL Balancing

Binary Tree Types