Binary Trees: Three Traversal Methods of Binary Trees, Recursive Implementation Made Super Simple

A binary tree is a very basic data structure where each node has at most two child nodes (left and right subtrees). Traversing a binary tree means visiting each node in a specific order, similar to browsing shelves in a supermarket. Today, we’ll learn the three most classic traversal methods for binary trees: preorder, inorder, and postorder, implemented recursively for simplicity and clarity!

First, Understand: What is Recursion?¶

Recursion is like a “Matryoshka doll”—a function calls itself, but each time with a smaller “scope” until it hits a termination condition (e.g., stopping when “nesting” down to an empty box). For example, to calculate 1+2+3+…+n, the recursive approach is to first compute 1+2+…+(n-1), then add n to the result.

Three Traversal Orders of Binary Trees¶

The key to traversal order is the position of the root node. The three methods are:
- Preorder Traversal: Root → Left Subtree → Right Subtree (visit the root first, then left shelf, then right shelf)
- Inorder Traversal: Left Subtree → Root → Right Subtree (first left shelf, then root, then right shelf)
- Postorder Traversal: Left Subtree → Right Subtree → Root (first left and right shelves, then root)

Understanding Traversal with an Example¶

Let’s use a concrete binary tree for visualization:

    1
   / \
  2   3
 / \
4   5

Structure: Root is 1, left child’s root is 2, right child’s root is 3; 2 has left child 4 and right child 5.

1. Preorder Traversal (Root → Left → Right)¶

Order: Visit the root, then traverse the left subtree, then the right subtree.

Recursive Implementation:¶

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(root):
    if root is None:  # Termination condition: return if node is empty
        return
    print(root.val, end=" ")  # Visit root
    preorder(root.left)       # Recurse left subtree
    preorder(root.right)      # Recurse right subtree

Traversal Process (using the example tree):¶

• Start at root 1, print 1 → enter left subtree (node 2)
• Print 2 → enter left subtree (node 4)
• Node 4 has no children, print 4 → return
• Back to node 2, enter right subtree (node 5), print 5 → return
• Back to root 1, enter right subtree (node 3), print 3 → done

Result: 1 2 4 5 3

2. Inorder Traversal (Left → Root → Right)¶

Order: Traverse the left subtree first, then visit the root, then the right subtree.

Recursive Implementation:¶

def inorder(root):
    if root is None:
        return
    inorder(root.left)        # Recurse left subtree
    print(root.val, end=" ")  # Visit root
    inorder(root.right)       # Recurse right subtree

Traversal Process:¶

• Recurse to the deepest left (node 4), print 4 → return
• Back to node 2, print 2 → enter right subtree (node 5), print 5 → return
• Back to root 1, print 1 → enter right subtree (node 3), print 3 → done

Result: 4 2 5 1 3

3. Postorder Traversal (Left → Right → Root)¶

Order: Traverse the left subtree, then the right subtree, then visit the root.

Recursive Implementation:¶

def postorder(root):
    if root is None:
        return
    postorder(root.left)      # Recurse left subtree
    postorder(root.right)     # Recurse right subtree
    print(root.val, end=" ")  # Visit root

Traversal Process:¶

• Recurse to the deepest left (node 4), print 4 → return
• Recurse to node 5, print 5 → return
• Back to node 2, print 2 → recurse right subtree (node 3), print 3 → return
• Back to root 1, print 1 → done

Result: 4 5 2 3 1

Core Differences Between the Three Traversals¶

Key Ideas of Recursion¶

1. Termination Condition: When the current node is empty (root is None), return immediately to stop recursion.
2. Recursive Logic: Depending on the traversal order, process the current node (root) first, then recursively traverse left/right subtrees (order varies).
3. “Top-Down” Execution: Start from the root, go deeper to leaf nodes, then backtrack to process parent nodes.

By implementing these three traversals recursively, the core is “clarity of order and recursive calls.” Remember the “root position” for each traversal to write the recursive function easily. Drawing tree structures and tracing through the recursive steps will help you master this quickly!