Binary Tree Inorder Traversal - Recursive, Iterative & Morris Solutions

Introduction

Inorder traversal follows the Left → Root → Right pattern:

1. Traverse the left subtree
2. Visit the current node
3. Traverse the right subtree

The BST Magic ✨

For a Binary Search Tree (BST), inorder traversal visits nodes in sorted ascending order! This is the most important property of inorder traversal.

BST:       4
          / \
         2   6
        / \ / \
       1  3 5  7

Inorder: 1 → 2 → 3 → 4 → 5 → 6 → 7  (Sorted!)

Why Interviewers Love It

• Essential for BST problems (kth smallest, validate BST, etc.)
• Tests understanding of recursion and stack manipulation
• Morris traversal demonstrates space optimization mastery
• Foundation for many advanced tree algorithms

When to Use Inorder

• Kth smallest/largest in BST (LC 230)
• Validate BST (LC 98)
• Convert BST to sorted list
• Find BST floor/ceiling
• Recover BST (LC 99)

Visual Intuition

        1
       / \
      2   3
     / \
    4   5

Inorder: 4 → 2 → 5 → 1 → 3
         (Left→Root→Right)

Visit order:
  Step 1: Go left to 2, then left to 4
  Step 2: Visit 4 (no children)
  Step 3: Backtrack, Visit 2
  Step 4: Go right, Visit 5
  Step 5: Backtrack to 1, Visit 1
  Step 6: Go right, Visit 3

Interactive Visualizer

Watch the algorithm step through the tree. Compare recursive vs iterative vs Morris!

Method:RecursiveIterativeMorris

Speed:0.5x1x2x4x

Inorder (Left→Root→Right) - Iterative

Step 1 / 0INIT

Ready to start

Stack

Empty

Result

[]

Current

Visited

In Stack

⟲ Reset← Prev▶ PlayNext →

Solution 1: Recursive Approach

The most intuitive solution: go left, visit, go right.

Code Template

JavaPythonJavaScript

Loading...

How It Works

1. Base case: If node is null, return
2. Recurse left: Process entire left subtree first
3. Visit root: Add current node’s value
4. Recurse right: Then process right subtree

The call stack automatically handles the “go back up” logic.

Solution 2: Iterative Approach (Stack)

Key insight: We need to go as left as possible before visiting any node.

Code Template

JavaPythonJavaScript

Loading...

Step-by-Step Walkthrough

Tree:       1
           / \
          2   3
         /
        4

Step 1: Push 1, go left       Stack: [1]
Step 2: Push 2, go left       Stack: [1, 2]
Step 3: Push 4, go left       Stack: [1, 2, 4]
Step 4: No left, pop 4, visit Result: [4]
Step 5: No right, pop 2, visit Result: [4, 2]
Step 6: Go right (none), pop 1, visit Result: [4, 2, 1]
Step 7: Go right to 3
Step 8: Push 3, no left, pop 3, visit Result: [4, 2, 1, 3]

Final: [4, 2, 1, 3]

The Pattern

while (current exists OR stack not empty):
    1. Go leftmost (push all left nodes)
    2. Pop and visit
    3. Go right (becomes new current)

Solution 3: Morris Traversal (O(1) Space)

Morris traversal uses threading to eliminate the stack. It temporarily creates links from predecessors back to their successors.

Key Difference from Preorder

• Preorder Morris: Visit before creating thread
• Inorder Morris: Visit after returning via thread

Code Template

JavaPythonJavaScript

Loading...

How Threading Works

Original:              With Thread:
      4                     4
     / \                   / \
    2   6                 2   6
   / \                   / \
  1   3                 1   3
                             \
                              → (thread to 4)

Thread: 3's right points to 4 (its inorder successor)

Visit Timing

For inorder, we visit when:
1. No left child → visit, go right
2. Thread exists (returning) → visit, remove thread, go right

NOT when creating thread! That's for preorder.

LeetCode 94: Binary Tree Inorder Traversal (LC 94)

The classic inorder problem. All three solutions work directly.

Example:

Input: root = [1,null,2,3]
    1
     \
      2
     /
    3

Output: [1, 3, 2]

Problem 2: Kth Smallest in BST (LC 230)

Since inorder gives sorted order for BST, just return the kth element!

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        current = stack.pop();
        if (--k == 0) return current.val;  // Found kth!
        
        current = current.right;
    }
    
    return -1;  // k > tree size
}

Problem 3: Validate BST (LC 98)

Use inorder and check if each value is greater than the previous:

def isValidBST(root: Optional[TreeNode]) -> bool:
    stack = []
    current = root
    prev = float('-inf')
    
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        if current.val <= prev:  # Must be strictly increasing
            return False
        prev = current.val
        
        current = current.right
    
    return True

Complexity Analysis

Method	Time	Space	Notes
Recursive	O(n)	O(h)	h = height, O(n) worst case
Iterative	O(n)	O(h)	Explicit stack
Morris	O(n)	O(1)	Each edge visited at most twice

Space Comparison

       Balanced Tree         Skewed Tree
           O                     O
          / \                     \
         O   O                     O
        / \ / \                     \
       O  O O  O                     O

Stack depth: O(log n)         Stack depth: O(n)

Common Mistakes

1. Iterative: Forgetting Outer Condition

// WRONG: Only checks stack
while (!stack.isEmpty()) {  // Misses initial current
    // ...
}

// CORRECT: Check both
while (current != null || !stack.isEmpty()) {
    // ...
}

2. Morris: Wrong Visit Timing

# WRONG for inorder: Visiting before going left
if not predecessor.right:
    result.append(current.val)  # Too early!
    predecessor.right = current
    current = current.left

# CORRECT: Visit when returning
if predecessor.right:  # Thread exists
    predecessor.right = None
    result.append(current.val)  # Visit now!
    current = current.right

3. Not Handling Empty Tree

// Always check for null root first
function inorderTraversal(root) {
  if (!root) return [];  // Don't forget!
  // ...
}

Edge Cases

1. Empty tree: Return []
2. Single node: Return [root.val]
3. Left-skewed tree: Tests maximum stack depth
4. Right-skewed tree: Tests iterative logic
5. Complete binary tree: Standard balanced case

Interview Tips

How to Explain Inorder

1. “Inorder means Left → Root → Right”
2. “For BST, this gives sorted order”
3. “Stack simulates the call stack in recursion”
4. “Morris creates temporary threads to save space”

Follow-up Questions

Question	Answer
”Why use inorder for BST?”	Gives sorted ascending order
”How to get descending order?”	Right → Root → Left (reverse inorder)
“O(1) space possible?”	Yes, Morris traversal
”What if can’t modify tree?”	Use stack, O(h) space

Comparison with Other Traversals

Property	Preorder	Inorder	Postorder
Order	Root→L→R	L→Root→R	L→R→Root
BST sorted?	No	Yes ✓	No
Use case	Copy tree	BST ops	Delete tree
Visit timing	Before children	Between children	After children

Summary

Aspect	Recursive	Iterative	Morris
Simplicity	⭐⭐⭐	⭐⭐	⭐
Space	O(h)	O(h)	O(1)
Modifies Tree	No	No	Yes (temp)
Best for	Learning	Interviews	Optimization

Key Patterns to Remember:

1. Inorder = Left → Root → Right
2. BST + Inorder = Sorted order
3. Iterative: Push all left, pop & visit, go right
4. Morris: Visit when thread EXISTS (not when creating)

Inorder traversal is crucial for BST problems. Master all three implementations!