Course contentsShow
← Computer Science
Lesson 470 of 2,87211. Binary TreesFree lesson

Implementing Preorder Recursively

Writing recursive preorder traversal: process current node, recurse left, recurse right, with base case for null.

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:

  1. Base case: If the current node is null, do nothing and return
  2. Process the current node (print it, add to a list, etc.)
  3. Recurse left: Call the function on the left child
  4. 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:

  1. Process A
  2. Recurse to B (process B, then its children)
  3. 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.