Preorder Traversal
Overview
Preorder Traversal is a variation of Tree DFS where the root is processed BEFORE its children: Root (Self) -> Left Child -> Right Child.
Because it processes the parent node immediately upon discovery, Preorder is used whenever you need to aggressively explore or duplicate a tree structure.
If you traverse a tree using Preorder and insert those exact values sequentially into a new, blank tree, you will perfectly clone the original structure. If you try doing that with an Inorder traversal, you will end up creating a degenerate, unbalanced Linked List instead of a clone.
Syntax
public class Preorder {
static class TreeNode {
int val; TreeNode left, right;
}
public void preorder(TreeNode root) {
if (root == null) return;
// 1. Process the Root (Self) FIRST
System.out.print(root.val + " ");
// 2. Go down the Left side
preorder(root.left);
// 3. Go down the Right side
preorder(root.right);
}
}Common Pitfalls
- Using Preorder when you meant to use Inorder. This is a common mistake that ruins sorting algorithms on BSTs.
- Iterative implementation complexity. While recursive Preorder is 3 lines, iterative Preorder requires explicitly managing a Stack, pushing the Right child first, then the Left child, so that the Left child is popped first.
Interview Questions
Cloning a tree structure. By visiting the root first, you can instantiate the parent node in the clone tree before you attempt to attach the child nodes to it.
Real-World Example
Cloning an exact binary tree structure into a new object in memory. You cannot attach a left child to a parent if the parent hasn't been instantiated yet, which is why Preorder (Root first) is mandatory.
class TreeNode { int val; TreeNode left, right; TreeNode(int v){val=v;} }
public class TreeCloner {
public TreeNode cloneTree(TreeNode root) {
if (root == null) return null;
// 1. Process Root: Create the new parent node FIRST
TreeNode newRoot = new TreeNode(root.val);
// 2. Recursively clone and attach the left side
newRoot.left = cloneTree(root.left);
// 3. Recursively clone and attach the right side
newRoot.right = cloneTree(root.right);
return newRoot;
}
}Check Your Knowledge
Test your understanding of Preorder Traversal with these quick questions.