Q&A

What is pre-order traversal?

By AlgoInsight Team2026-06-07data-structures

Overview

Tree traversal means visiting every node exactly once in some order. The three classic depth-first orders differ only in when you visit the root relative to its subtrees: pre-order (root first), in-order (root in the middle), post-order (root last). Pre-order's "root before children" property makes it natural for reproducing a tree's structure.

graph TD
    A((1)) --> B((2))
    A --> C((3))
    B --> D((4))
    B --> E((5))
    C --> F((6))
    style A fill:#1e1b4b,color:#fff

For this tree, pre-order (Root→Left→Right) visits: 1, 2, 4, 5, 3, 6.

The Rule: Root → Left → Right

1. Visit (process) the current node.
2. Recur on the left subtree.
3. Recur on the right subtree.

The root is always handled before descending - that's the defining trait.

Recursive Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def preorder(node, result):
    if node is None:
        return
    result.append(node.val)     # 1. visit root
    preorder(node.left, result) # 2. left subtree
    preorder(node.right, result)# 3. right subtree
    return result

# preorder(root, []) -> [1, 2, 4, 5, 3, 6]

Iterative Implementation (explicit stack)

Recursion uses the call stack implicitly; you can do it explicitly with a stack. Push the right child before the left, so the left is processed first (LIFO):

def preorder_iter(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)        # visit
        if node.right: stack.append(node.right)  # push right first
        if node.left:  stack.append(node.left)   # so left pops first
    return result

The Three DFS Orders Compared

For the tree above:

(There's also level-order/BFS, which uses a queue and visits by depth.)

What Pre-order Is Good For

• Copying/cloning a tree - create each node before its children, mirroring structure.
• Serializing a tree - pre-order (with null markers) uniquely encodes structure for later reconstruction.
• Prefix (Polish) notation - pre-order of an expression tree yields prefix form (+ a b).
• Directory listing - print a folder before its contents.

Complexity

• Time: O(n) - every node visited once.
• Space: O(h) for the stack/recursion, where h is the tree height (O(n) worst case for a skewed tree, O(log n) for balanced).

Why This Matters in Interviews

Tree traversals are bread-and-butter interview material. Know all three DFS orders, be able to write pre-order both recursively and iteratively (the iterative version's "push right before left" is a classic detail), and state its uses (cloning, serialization, prefix expressions). Distinguishing the three by when the root is visited is the clean mental model. A common follow-up: reconstruct a tree from pre-order + in-order arrays.

Common Pitfalls

• Mixing up the orders - pre-order is root first, post-order is root last.
• In the iterative version, pushing left before right (yields the wrong order).
• Forgetting the null/base case → infinite recursion or crashes.
• Confusing in-order (which gives sorted output for a BST) with pre-order.

References

• Tree traversal: https://en.wikipedia.org/wiki/Tree_traversal
• LeetCode 144 "Binary Tree Preorder Traversal": https://leetcode.com/problems/binary-tree-preorder-traversal/

More answers