Inorder Traversal
Recursively traverses the left subtree, visits the root, then the right subtree.
Visits the root first, then recursively traverses left and right subtrees.
Preorder traversal visits each node in a binary tree in the order: root, left subtree, right subtree. The root is always processed first, before any of its descendants. This traversal strategy is one of three depth-first approaches formalized in the early study of tree data structures, dating back to the foundational work on recursive data structures in the 1950s and 1960s. The name "preorder" reflects the fact that the current node is processed before (pre-) its children.
For a tree with root A, left child B (with children D and E), and right child C (with children F and G), preorder visits: A, B, D, E, C, F, G. Notice that the algorithm fully explores the left branch before moving to the right branch -- this is the hallmark of depth-first search.
The recursive implementation is elegant and concise. In pseudocode: call visit(node), then preorder(node.left), then preorder(node.right). An iterative version uses an explicit stack: push the root, then repeatedly pop a node, visit it, push its right child, and push its left child (right first so that left is processed first due to LIFO ordering).
| Case | Time | Space |
|---|---|---|
| All cases | O(n) | O(h) where h = tree height |
Every node is visited exactly once, giving linear time. The space comes from the call stack (recursive) or explicit stack (iterative), which holds at most h frames where h is the tree height. For a balanced tree, h = O(log n). For a degenerate (skewed) tree, h = O(n), making the worst-case space linear.
Preorder traversal creates a natural serialization of a tree. If you record the values in preorder and include null markers for missing children, you can reconstruct the exact tree from that sequence. This property makes preorder the standard choice for saving trees to files, transmitting them over a network, or storing them in databases. JSON and XML document trees are often serialized in what is effectively a preorder walk.
When you insert values into a new Binary Search Tree in the preorder sequence of an existing BST, you reconstruct an identical tree. This makes preorder the correct traversal for cloning or deep-copying a BST while preserving its structure.
In expression trees -- where internal nodes are operators and leaves are operands -- preorder traversal produces prefix notation (also called Polish notation), invented by Polish logician Jan Lukasiewicz in 1924. For example, the expression (3 + 5) * 2 stored as a tree yields * + 3 5 2 in prefix form. Prefix notation eliminates the need for parentheses and is straightforward to evaluate using a right-to-left stack scan.
Preorder traversal mirrors how a file system lists a directory before listing its contents. When you run a recursive directory listing, you see the folder name first, then its files and subfolders. The find command on Unix-like systems and the Windows dir /s command both walk directory trees in essentially preorder fashion.
Choose preorder traversal when you need to process a node before its descendants. Common scenarios include serializing or deserializing tree structures, creating deep copies of trees, generating prefix expressions from expression trees, and implementing tree-based protocols where parent information must be transmitted before child information. If you need sorted output from a BST, use inorder instead. If you need to compute bottom-up aggregates, use postorder.