Inorder Traversal: Left-Root-Right
What you'll learn: You'll discover how to visit every node in a binary tree by going left first, then processing the root, then going right—creating a naturally sorted order in binary search trees.
The Core Idea
Inorder traversal follows a specific pattern: Left-Root-Right. For any given node, you first completely traverse its left subtree, then visit (process) the node itself, then completely traverse its right subtree.
Think of it like reading a family tree from left to right across generations—you visit the leftmost descendants first, work your way to the middle ancestor, then explore the right side of the family.
How It Works
Starting at the root, the algorithm:
- Recursively traverse the left subtree using inorder
- Visit (print/process) the current node
- Recursively traverse the right subtree using inorder
For a tree with root 5, left child 3, and right child 8:
- First visit 3 (leftmost)
- Then visit 5 (root)
- Finally visit 8 (rightmost)
- Output:
3, 5, 8
Why It Matters
Inorder traversal has a special property: it visits nodes in ascending sorted order when applied to a binary search tree. This makes it incredibly useful for retrieving elements in sorted sequence without needing to sort them separately.
Unlike preorder (which visits root first), inorder places the root "in" the middle of its children—hence the name.
Comparison to Preorder
Where preorder gave us 5, 3, 8 (root first), inorder gives us 3, 5, 8 (root between its children). The traversal order fundamentally changes based on when you process the root node relative to its subtrees.
Key Takeaway: Inorder traversal visits nodes in Left-Root-Right order, naturally producing sorted output for binary search trees by processing each node after its left subtree but before its right subtree.