Pre Order Traversal

What Is Pre Order Traversal?

Pre order traversal is a systematic way to visit all nodes in a tree using a depth-first strategy. The key idea is to process ("visit") each node before exploring its children.

• Binary tree order: Root, Left subtree, Right subtree (often written as R-L-R).
• N-ary tree order: Visit node, then visit children from left to right.

Example

        A
       / \
      B   C
     / \   \
    D   E   F

Pre order sequence: A, B, D, E, C, F

Algorithm (High Level)

1. Visit the current node (process its value).
2. Recursively traverse the left (or first) child subtree.
3. Recursively traverse the right (or remaining) child subtree.

For an iterative version, use an explicit stack: push the root, pop a node, visit it, then push its children in reverse order of the desired visit so the leftmost child is processed next.

Recursive Implementation

Binary Tree (Python)

def preorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.val)  # visit
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return result

N-ary Tree (Pseudocode)

function preorder(node):
    if node is null: return
    visit(node)
    for child in node.children:
        preorder(child)

Iterative Implementation (Using a Stack)

Binary Tree (Python)

def preorder_iterative(root):
    if not root:
        return []
    stack = [root]
    out = []
    while stack:
        node = stack.pop()
        out.append(node.val)
        # Push right first so left is processed next
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out

Binary Tree (JavaScript)

function preorder(root) {
  if (!root) return [];
  const res = [];
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return res;
}

Complexity

• Time: O(n), where n is the number of nodes (each node is visited once).
• Space: O(h), where h is the height of the tree (due to recursion or the explicit stack). In the worst case (skewed tree), h = O(n); in a balanced tree, h = O(log n).

Common Uses

• Serialization and cloning of trees (prefix form), often with null markers for missing children.
• Evaluating or printing expression trees in prefix (Polish) notation.
• Generating root-to-leaf paths or performing side-effectful visits (e.g., setting indexes, computing sizes before visiting children).
• Precomputing or exporting hierarchical structures (menus, file systems, ASTs).

Relationship to Other Traversals

• In order (binary trees only): Left, Root, Right — often yields sorted order in a BST.
• Post order: Left, Right, Root — useful for deleting trees, computing subtree values, or evaluating postfix expressions.
• Breadth-first (level order): Visits nodes level by level, not depth-first.

Variations and Nuances

• N-ary trees: Visit node, then children in order.
• Threaded or implicit trees: Pre order still applies; child access differs.
• Iterative vs recursive: Iterative avoids recursion depth limits; recursive is often simpler.

Pitfalls and Tips

• Always handle null roots gracefully.
• For iterative versions, push the right child before the left to maintain left-first visitation.
• Be mindful of recursion depth on very deep trees; consider iterative approach where needed.
• When serializing, include markers for missing children to support unambiguous reconstruction.

Quick Practice

1. Write a function to return the pre order sequence of a binary tree.
2. Modify it to work for an n-ary tree with a children list.
3. Serialize a binary tree with pre order using a sentinel (e.g., #) for nulls, then write the corresponding deserializer.

Next Topic