Traversal

Pre-Order (Root, Left, Right)

Visit the root FIRST, then traverse left subtree, then right. Useful for making a copy of the tree or serializing it — because you process the parent before its children, you can reconstruct the structure.

O(n)

O(h)

How It Works

Pre-order traversal visits each node before either of its subtrees: process the root, recurse left, recurse right. Because a parent is always seen before its children, the output stream encodes enough information to rebuild the tree's structure top-down — which is exactly why serialization and tree-copying rely on this order. Iteratively, a stack replaces recursion: pop a node, visit it, then push the right child before the left so the left is processed first.

Every node is visited exactly once, so time is O(n). Space is O(h) for the recursion stack or explicit stack, where h is the tree height — O(log n) for balanced trees, degrading to O(n) for a skewed chain. No comparisons or re-visits are needed, so it is already optimal for any task that must touch every node.

Step-by-Step Visualization

Pre-order: Root, Left, Right

Visit1 (root)

Output[1]

1/3

Code

Java

static List<Integer> preorder(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);

  while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    if (node == null) continue;
    result.add(node.val);
    stack.push(node.right);
    stack.push(node.left);
  }
  return result;
}

// Tree: [1,2,3,4,5] → Pre-order: [1,2,4,5,3]

Tips & Gotchas

1Visit root first, then left subtree, then right subtree

2Use a stack iteratively: push right child first, then left

3Pre-order is useful for copying/serializing trees

Practice Problems

1Binary Tree Preorder Traversal
2Serialize and Deserialize Binary Tree
3Flatten Binary Tree to Linked List
4Construct Binary Tree from Preorder and Inorder Traversal

About the Traversal Pattern

There are four ways to visit every node in a tree. Three use DFS (going deep before going wide) with different orderings, and one uses BFS (going wide before going deep). Each ordering is useful for different problems.

Key insight

Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.

Common Trees Interview Problems

Maximum Depth of Binary Tree
Validate BST
Binary Tree Level Order Traversal
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Diameter of Binary Tree

Frequently Asked Questions

Why is pre-order the natural choice for copying or serializing a tree?

Pre-order emits each parent before its children, so a reader consuming the stream can create the root first and then attach children as they arrive. Orders that visit the root later (in-order or post-order) leave the reader without a parent to attach to until much of the subtree has been read.

In the iterative version, why push the right child before the left?

A stack is last-in-first-out, so whatever you push last is popped next. Pushing right then left guarantees the left subtree is fully explored before the right, preserving the root-left-right order.

Does pre-order versus in-order change the time complexity?

No. All three DFS orders visit every node exactly once, so they are all O(n) time and O(h) space. The choice only affects when the root is processed relative to its subtrees, which determines which problems each order fits.