Implementing Preorder Recursively
You'll learn how to code a recursive preorder traversal that visits the root first, then left and right subtrees.
The Recursive Pattern
Remember that preorder traversal follows the Root-Left-Right order. Recursion is a natural fit because each subtree is itself a tree, and we can apply the same three-step process to every node we encounter.
The algorithm is beautifully simple:
- Base case: If the current node is
null, do nothing and return - Process the current node (print it, add to a list, etc.)
- Recurse left: Call the function on the left child
- Recurse right: Call the function on the right child
The Code Structure
Here's what recursive preorder traversal looks like:
function preorderTraversal(node):
if node is null:
return // base case
process(node) // visit root
preorderTraversal(node.left) // traverse left subtree
preorderTraversal(node.right) // traverse right subtree
Why It Works
Think of it like exploring a family tree: you meet someone (process the root), then explore their entire left branch of descendants before moving to their right branch. At each person you meet, you repeat this same pattern.
The null check is critical—it stops the recursion from crashing when it reaches leaves (whose children are null).
Example Walkthrough
For a tree with root A, left child B, right child C:
- Process
A - Recurse to
B(process B, then its children) - After B's subtree completes, recurse to
C
Key Takeaway: Recursive preorder traversal combines a null base case with three steps: process current node, recurse left, recurse right—elegantly mirroring the Root-Left-Right definition.