Chapter 24: DSA In-order Traversal
DSA In-order Traversal – Let’s understand this topic properly, like I’m sitting next to you with a whiteboard, drawing the tree step by step, walking through every single move slowly, showing exactly what happens at each moment, and explaining why in-order is special compared to pre-order and post-order.
What is In-order Traversal?
In-order traversal is one of the three classic depth-first traversals of a binary tree.
The name in-order tells you the exact rule:
In means in the middle → We visit (process/print) the root node in between visiting its left and right subtrees.
So the visiting order is:
Left subtree → Root → Right subtree
This is the exact sequence you follow:
- Recursively traverse the left subtree
- Visit the current node (process it — print, store, compare, etc.)
- Recursively traverse the right subtree
Visual Rule – Very easy way to remember
Imagine you are walking around the tree like this:
|
0 1 2 3 4 5 6 |
Left subtree first ──→ Visit root here ──→ Right subtree |
Or think of it as:
|
0 1 2 3 4 5 6 7 8 9 10 11 |
← Visit here (middle) ┌───────┐ │ │ ┌────┴────┐ │ │ │ │ Left Right |
In-order = “Left first, then root, then right”
Classic Example Tree (we’ll use this for everything)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 |
In-order traversal of this tree gives:
7 4 2 5 8 1 3 9 6
Let’s see exactly why — step by step.
Step-by-step walkthrough (very detailed)
Start at root = 1
- We first go to left subtree of 1 → node 2
- Go to left of 2 → node 4
- Go to left of 4 → node 7
- 7 has no left → visit 7 → print 7
- 7 has no right → backtrack
- Now visit 4 → print 4
- Go to right of 4 → none → backtrack
- Go to left of 4 → node 7
- Now visit 2 → print 2
- Go to right of 2 → node 5
- 5 has no left → visit 5 → print 5
- Go to right of 5 → node 8
- 8 has no left → visit 8 → print 8
- 8 has no right → backtrack
- backtrack from 5 → backtrack from 2
- Go to left of 2 → node 4
- Now we visit root → print 1
- Now go to right subtree of root → node 3
- 3 has no left
- visit 3 → print 3
- Go to right of 3 → node 6
- Go to left of 6 → node 9
- 9 has no left → visit 9 → print 9
- 9 has no right → backtrack
- visit 6 → print 6
- 6 has no right → done
- Go to left of 6 → node 9
Final output: 7 4 2 5 8 1 3 9 6
In-order Traversal Code (most common interview versions)
1. Recursive (cleanest and most natural)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def inorderTraversal(root): result = [] def helper(node): if not node: return # Step 1: Left subtree first helper(node.left) # Step 2: Visit root in the middle result.append(node.val) # Step 3: Right subtree helper(node.right) helper(root) return result |
2. Iterative version using Stack (very frequently asked)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
def inorderTraversal(root): result = [] stack = [] current = root while current or stack: # Go as far left as possible while current: stack.append(current) current = current.left # Now we are at the leftmost node current = stack.pop() result.append(current.val) # visit # Move to right subtree current = current.right return result |
This is the classic iterative in-order — very important to understand and write quickly in interviews.
Why is In-order Traversal Special?
| Use case | Why in-order is the best choice |
|---|---|
| Get sorted order of elements | In a BST, in-order gives nodes in ascending order |
| Validate Binary Search Tree | In-order should be strictly increasing |
| Recover BST after two nodes are swapped | In-order helps find the swapped positions |
| Kth smallest / largest element in BST | Do in-order and stop at kth node |
| Print tree in sorted order without extra space | In-order is natural for BST |
| Some tree flattening / conversion problems | In-order sequence is useful |
Key sentence for interviews:
“If the problem involves a Binary Search Tree and you need the elements in sorted order, the answer is almost always in-order traversal.”
In-order vs Pre-order vs Post-order – Quick Comparison
| Traversal | Visit order | Root position | BST sorted order? | Most famous use |
|---|---|---|---|---|
| Pre-order | Root → Left → Right | First | No | Copy tree, prefix expr |
| In-order | Left → Root → Right | Middle | Yes | Sorted order, BST problems |
| Post-order | Left → Right → Root | Last | No | Delete tree, postfix expr |
Summary – In-order Traversal in one line each
- Visit order: Left → Root → Right
- Root is processed after left subtree but before right subtree
- Recursive version is very clean and intuitive
- Iterative version uses stack + go left as much as possible
- Time complexity: O(n) — visits every node exactly once
- Space complexity: O(h) recursive / O(n) worst iterative (skewed tree)
- Most important traversal for Binary Search Trees
- One of the first things interviewers expect you to write fluently
Would you like to continue with the next related topic?
Very natural next steps:
- Post-order Traversal (complete the DFS trio)
- All three traversals (pre/in/post) on same tree with comparison
- Iterative In-order step-by-step dry run (very important)
- In-order traversal applications in BST (kth smallest, validate BST, etc.)
- Morris Traversal (O(1) space in-order – advanced but asked sometimes)
Just tell me which one you want next — I’ll explain it with the same level of detail, visuals, and step-by-step clarity! 😊
