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

Implementing Inorder Recursively

Writing recursive inorder traversal: recurse left, process current node, recurse right, handles null nodes naturally.

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:

  1. Recurse left — call the function on the left child
  2. Process current node — do whatever you need (print, store, etc.)
  3. 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.