Pre-Order Traversal — Root, Left, Right

Pre-Order Traversal (NLR)

Pre-order traversal visits nodes in the order: Node, Left subtree, Right subtree. The root is always the first element in the output, which makes pre-order useful for tree serialization and reconstruction.

Recursive Implementation

PREORDER(node):
  if node is NULL: return
  visit(node)          // process root first
  PREORDER(node.left)
  PREORDER(node.right)

Example

        4
       / \
      2   6
     / \ / \
    1  3 5  7

Pre-order result: [4, 2, 1, 3, 6, 5, 7]

The root (4) appears first, followed by the entire left subtree [2, 1, 3], then the entire right subtree [6, 5, 7].

Tree Serialization and Deserialization

Pre-order traversal can uniquely represent a BST because the first element is always the root, and you can determine the left/right split by finding where values become larger than the root. This property is used in:

• Serializing a tree to a string or file
• Transmitting tree structures over a network
• Storing tree snapshots for undo/redo functionality

Relationship to DFS

Pre-order traversal is essentially a depth-first search (DFS) on the tree. It explores as deep as possible along the left branch before backtracking. This is why DFS on a tree and pre-order traversal produce the same visitation pattern when going left-first.

Time and Space Complexity

• Time: O(n) — visits every node exactly once
• Space: O(h) — recursion depth equals tree height