Overview
Preorder traversal is a depth-first traversal that visits nodes in the order Root, Left, Right. It processes a node before descending into either of its subtrees.
Because the root is emitted first, preorder captures the tree's shape top-down, which makes it the standard choice for copying a tree or serializing it to a form that can rebuild the exact same structure.
How Preorder Traversal works
- Visit (process) the current node first.
- Recursively traverse the entire left subtree.
- Recursively traverse the entire right subtree.
- Return on an empty subtree (null); the root always appears before its descendants.
When to use it
- Making a deep copy of a tree, since the parent is created before its children.
- Serializing a tree to disk or network so it can be reconstructed identically.
- Emitting prefix (Polish) notation from an expression tree.
Complexity analysis
Preorder traversal touches each of the n nodes once, so it runs in O(n) time. Its recursion stack is bounded by the tree height h, giving O(h) space — O(log n) when balanced and O(n) for a degenerate tree.
Frequently asked questions
Why is preorder preferred for serializing a tree?
It writes each parent before its children, so a reader can recreate nodes top-down and attach children as it goes — recording null markers lets it rebuild the exact structure unambiguously.
How does preorder differ from inorder and postorder?
All three are depth-first and O(n); they differ only in when the root is visited — first for preorder, between the subtrees for inorder, and last for postorder.