Implementing Inorder Recursively
You'll learn how to write a recursive function that visits every node in a binary tree using inorder (left-root-right) traversal.
The Core Idea
Remember from the previous lesson that inorder traversal visits nodes in left-root-right order. Now we'll implement it recursively. The beauty of recursion here is that it naturally handles the "left subtree first" requirement: we simply call our function on the left child before processing the current node.
Here's the pattern:
- Recurse left — call the function on the left child
- Process current node — do whatever you need (print, store, etc.)
- Recurse right — call the function on the right child
Recursive Implementation
def inorder(node):
# Base case: if node is null, do nothing
if node is None:
return
# Step 1: Recursively visit left subtree
inorder(node.left)
# Step 2: Process current node
print(node.data)
# Step 3: Recursively visit right subtree
inorder(node.right)
Why This Works
The recursion handles null children automatically — when we reach a leaf's child (which is None), the base case returns immediately. No special logic needed! Each recursive call manages its own "visit left, process me, visit right" sequence, and the call stack takes care of returning to parent nodes at the right time.
For a tree with nodes [4, 2, 5, 1, 3] (where 4 is root), calling inorder(root) produces: 1, 2, 3, 4, 5 — perfectly sorted for a binary search tree!
Key Takeaway: Recursive inorder traversal is elegantly simple: check for null, recurse left, process current, recurse right — the recursion naturally handles the tree structure and null nodes without extra conditional logic.