Skip to content

139. Binary Tree Inorder Traversal

🔗 LeetCode Problem: 94. Binary Tree Inorder Traversal
📊 Difficulty: Easy
🏷️ Topics: Binary Trees, DFS, Traversal, Stack, Recursion

Problem Statement

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1: 

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2: 

Input: root = []
Output: []

Example 3: 

Input: root = [1]
Output: [1]

Follow up: Recursive solution is trivial, could you do it iteratively?

Constraints: - The number of nodes in the tree is in the range [0, 100] - -100 <= Node.val <= 100

🌳 Visual Understanding - The Three Traversal Orders!

What is Traversal?

Traversal = Visiting every node in a specific ORDER

Three main DFS orders:
1. Inorder:   Left → Root → Right
2. Preorder:  Root → Left → Right  
3. Postorder: Left → Right → Root

Think of it as when you PROCESS the root!

Example Tree:

       1
      / \
     2   3
    / \
   4   5

Let's see all three traversals:

Inorder Traversal (Left → Root → Right):

Process order:
1. Go all the way LEFT first
2. Process ROOT
3. Then go RIGHT

Visual order:
       1 (3rd)
      / \
(2nd)2   3 (4th)
    / \
(1st)4  5

Result: [4, 2, 5, 1, 3]

Reading pattern: 
  - Start at leftmost leaf
  - Process nodes as you come back up
  - Think "ascending" for BST!

Preorder Traversal (Root → Left → Right):

Process order:
1. Process ROOT first
2. Then go LEFT
3. Then go RIGHT

Visual order:
       1 (1st)
      / \
(2nd)2   3 (5th)
    / \
(3rd)4  5 (4th)

Result: [1, 2, 4, 5, 3]

Reading pattern:
  - Process nodes as you encounter them
  - Top-down order
  - Good for copying tree structure!

Postorder Traversal (Left → Right → Root):

Process order:
1. Go LEFT
2. Then go RIGHT
3. Process ROOT last

Visual order:
       1 (5th)
      / \
(3rd)2   3 (4th)
    / \
(1st)4  5 (2nd)

Result: [4, 5, 2, 3, 1]

Reading pattern:
  - Process children before parent
  - Bottom-up order
  - Good for deletion/cleanup!

Memory Aid:

IN-order:    Left → IN (root) → Right
PRE-order:   PRE (root) → Left → Right
POST-order:  Left → Right → POST (root)

Position of ROOT tells you the order!

🧠 The AHA Moment - Understanding Inorder

Why Inorder is Special for BST:

Binary Search Tree (BST):
       4
      / \
     2   6
    / \ / \
   1  3 5  7

Inorder traversal: [1, 2, 3, 4, 5, 6, 7]
Result is SORTED! ✨

Why?
  Left < Root < Right (BST property)
  Inorder visits: Left → Root → Right
  So we get ascending order!

This is why inorder is important!

Recursive Pattern:

Inorder(node):
  1. Visit left subtree (recursive)
  2. Process current node
  3. Visit right subtree (recursive)

Simple recursive structure!

Visual Recursion Flow:

Tree:
    1
   / \
  2   3

Inorder execution:
  inorder(1):
    inorder(2):          ← Go left first
      inorder(null)      ← Left of 2
      process(2)         ← Process 2
      inorder(null)      ← Right of 2
    process(1)           ← Process 1
    inorder(3):          ← Go right
      inorder(null)      ← Left of 3
      process(3)         ← Process 3
      inorder(null)      ← Right of 3

Result: [2, 1, 3]

🧠 Recursive Thinking - Building the Solution

Base Case:

What's the simplest tree?
  → null (empty tree)

What to do with null?
  → Nothing! Just return

Base Case:
  if (node == null) return;

Or implicitly handled by checking before recursing

Recursive Case:

For any node:
  1. Recurse on LEFT subtree
     inorder(node.left)

  2. Process CURRENT node
     result.add(node.val)

  3. Recurse on RIGHT subtree
     inorder(node.right)

Order matters! This IS inorder!

The Complete Logic:

inorder(node, result):
  if node is null:
    return

  // LEFT
  inorder(node.left, result)

  // ROOT
  result.add(node.val)

  // RIGHT
  inorder(node.right, result)

🎯 Solution 1: Recursive (Trivial but Important)

Implementation:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    private void inorder(TreeNode node, List<Integer> result) {
        // Base Case: null node, nothing to process
        if (node == null) {
            return;
        }

        // LEFT: Recursively traverse left subtree
        // WHY? Inorder visits left first
        inorder(node.left, result);

        // ROOT: Process current node
        // WHY? After left, before right = INorder
        result.add(node.val);

        // RIGHT: Recursively traverse right subtree
        // WHY? Visit right last in inorder
        inorder(node.right, result);
    }
}

Ultra-Concise Version:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root != null) {
            result.addAll(inorderTraversal(root.left));   // LEFT
            result.add(root.val);                          // ROOT
            result.addAll(inorderTraversal(root.right));  // RIGHT
        }

        return result;
    }
}

🎯 Solution 2: Iterative with Stack (Important!)

The Challenge:

Recursion uses CALL STACK implicitly

To do iteratively:
  We need to simulate the call stack
  Use explicit Stack data structure!

Key insight:
  Stack remembers where to come back to
  Just like recursion does!

The Strategy:

Inorder: Left → Root → Right

Process:
  1. Go as far LEFT as possible (pushing onto stack)
  2. When can't go left, POP and process
  3. Then go RIGHT
  4. Repeat

Why this works:
  - Stack holds "pending" nodes
  - Pop gives us nodes in correct order
  - Right subtrees processed after parent

Implementation:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            // Step 1: Go as far LEFT as possible
            // Push all left nodes onto stack
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            // Step 2: Process node (ROOT in inorder)
            // Pop from stack - this gives us leftmost unprocessed node
            current = stack.pop();
            result.add(current.val);

            // Step 3: Go RIGHT
            // Now process right subtree
            current = current.right;
        }

        return result;
    }
}

Why Two Loops?

Outer while: Continue until all nodes processed
  - Runs while we have current node OR stack not empty

Inner while: Push all left nodes
  - Go left until we can't
  - Stack remembers the path

After inner loop:
  - current is null (no more left)
  - Pop gives us node to process
  - Then check its right subtree

🔍 Detailed Dry Run - Recursive

Tree:
       1
      / \
     2   3
    / \
   4   5

Complete Recursion Flow:

CALL STACK VISUALIZATION:

Level 0: inorder(1, [])
│
├─ node = 1, not null
│
├─ LEFT: inorder(2, []) ────────────────────────┐
│                                                │
│  Level 1: inorder(2, [])                      │
│  │                                             │
│  ├─ node = 2, not null                       │
│  │                                             │
│  ├─ LEFT: inorder(4, []) ──────────────────┐ │
│  │                                          │ │
│  │  Level 2: inorder(4, [])                │ │
│  │  │                                       │ │
│  │  ├─ node = 4, not null                 │ │
│  │  │                                       │ │
│  │  ├─ LEFT: inorder(null, [])            │ │
│  │  │  └─ return (nothing to do)          │ │
│  │  │                                       │ │
│  │  ├─ ROOT: result.add(4) → [4]          │ │
│  │  │                                       │ │
│  │  ├─ RIGHT: inorder(null, [4])          │ │
│  │  │  └─ return (nothing to do)          │ │
│  │  │                                       │ │
│  │  └─ return                              │ │
│  │                                          │ │
│  ├─ ROOT: result.add(2) → [4, 2]          │ │
│  │                                          │ │
│  ├─ RIGHT: inorder(5, [4, 2]) ────────────┐│ │
│  │                                         ││ │
│  │  Level 2: inorder(5, [4, 2])           ││ │
│  │  │                                      ││ │
│  │  ├─ node = 5, not null                ││ │
│  │  │                                      ││ │
│  │  ├─ LEFT: inorder(null, [4, 2])       ││ │
│  │  │  └─ return                          ││ │
│  │  │                                      ││ │
│  │  ├─ ROOT: result.add(5) → [4, 2, 5]   ││ │
│  │  │                                      ││ │
│  │  ├─ RIGHT: inorder(null, [4, 2, 5])   ││ │
│  │  │  └─ return                          ││ │
│  │  │                                      ││ │
│  │  └─ return                              ││ │
│  │                                          │ │
│  └─ return                                  │ │
│                                              │
├─ ROOT: result.add(1) → [4, 2, 5, 1]        │
│                                              │
├─ RIGHT: inorder(3, [4, 2, 5, 1]) ──────────┐
│                                             │
│  Level 1: inorder(3, [4, 2, 5, 1])         │
│  │                                          │
│  ├─ node = 3, not null                    │
│  │                                          │
│  ├─ LEFT: inorder(null, [4, 2, 5, 1])     │
│  │  └─ return                              │
│  │                                          │
│  ├─ ROOT: result.add(3) → [4, 2, 5, 1, 3] │
│  │                                          │
│  ├─ RIGHT: inorder(null, [4, 2, 5, 1, 3]) │
│  │  └─ return                              │
│  │                                          │
│  └─ return                                 │
│                                             │
└─ return result: [4, 2, 5, 1, 3]           │

FINAL: [4, 2, 5, 1, 3]

Visiting Order:

1. Visit 1 → go left to 2
2. Visit 2 → go left to 4
3. Visit 4 → go left to null (return)
4. Process 4 → add to result [4]
5. Visit 4's right (null) → return to 2
6. Process 2 → add to result [4, 2]
7. Visit 2's right (5)
8. Visit 5 → left is null
9. Process 5 → add to result [4, 2, 5]
10. Visit 5's right (null) → return to 1
11. Process 1 → add to result [4, 2, 5, 1]
12. Visit 1's right (3)
13. Visit 3 → left is null
14. Process 3 → add to result [4, 2, 5, 1, 3]
15. Visit 3's right (null) → done!

🔍 Detailed Dry Run - Iterative

Tree:
    1
   / \
  2   3

Stack Operations:

Initial:
  stack = []
  current = 1
  result = []

Iteration 1: Push left nodes
  Inner while: current = 1 (not null)
    push(1), current = 1.left = 2
  Inner while: current = 2 (not null)
    push(2), current = 2.left = null
  Inner while: current = null (stop)

  stack = [1, 2]  (bottom to top)
  current = null

Iteration 2: Process 2
  current = pop() = 2
  result.add(2) → result = [2]
  current = 2.right = null

  stack = [1]
  current = null

Iteration 3: Process 1
  Inner while: current = null (skip)
  current = pop() = 1
  result.add(1) → result = [2, 1]
  current = 1.right = 3

  stack = []
  current = 3

Iteration 4: Push 3
  Inner while: current = 3 (not null)
    push(3), current = 3.left = null
  Inner while: current = null (stop)

  stack = [3]
  current = null

Iteration 5: Process 3
  current = pop() = 3
  result.add(3) → result = [2, 1, 3]
  current = 3.right = null

  stack = []
  current = null

Iteration 6: Done
  current = null, stack = []
  Outer while: false (exit)

FINAL: [2, 1, 3]

📊 All Three Traversals - Complete Comparison

Recursive Implementations:

// INORDER: Left → Root → Right
private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);   // LEFT
    result.add(node.val);          // ROOT
    inorder(node.right, result);   // RIGHT
}

// PREORDER: Root → Left → Right  
private void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);          // ROOT (first!)
    preorder(node.left, result);   // LEFT
    preorder(node.right, result);  // RIGHT
}

// POSTORDER: Left → Right → Root
private void postorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    postorder(node.left, result);  // LEFT
    postorder(node.right, result); // RIGHT
    result.add(node.val);          // ROOT (last!)
}

Visual Comparison:

Tree:
       1
      / \
     2   3
    / \
   4   5

Inorder:   [4, 2, 5, 1, 3]  (Left → Root → Right)
           └─┘ └───┘ └───┘
           leaf subtree main

Preorder:  [1, 2, 4, 5, 3]  (Root → Left → Right)
           └┘ └──────┘ └┘
          root  left   right

Postorder: [4, 5, 2, 3, 1]  (Left → Right → Root)
           └──────┘ └──┘└┘
           subtree  sub root

📊 Complexity Analysis

Recursive Solution:

Time Complexity: O(n) 

Visit each node exactly once
At each node: O(1) work (add to list)
Total: n × O(1) = O(n)

Space Complexity: O(n) 

Recursion call stack: O(h) where h = height
Result list: O(n)

Best case (balanced): O(log n) + O(n) = O(n)
Worst case (skewed): O(n) + O(n) = O(n)

Overall: O(n)

Iterative Solution:

Time Complexity: O(n) 

Visit each node exactly once
Each node pushed and popped once
Total: O(n)

Space Complexity: O(n) 

Stack: O(h) where h = height
Result list: O(n)

Best case: O(log n) + O(n) = O(n)
Worst case: O(n) + O(n) = O(n)

Overall: O(n)

⚠️ Common Mistakes

Mistake 1: Wrong Order for Inorder

// ❌ WRONG - This is preorder, not inorder!
private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;

    result.add(node.val);          // ROOT first → PREORDER!
    inorder(node.left, result);
    inorder(node.right, result);
}

// ✓ CORRECT - Inorder
private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;

    inorder(node.left, result);    // LEFT first
    result.add(node.val);          // ROOT in middle
    inorder(node.right, result);   // RIGHT last
}

Mistake 2: Iterative - Forgetting Inner Loop

// ❌ WRONG - Only pushes one left node
while (current != null || !stack.isEmpty()) {
    if (current != null) {
        stack.push(current);
        current = current.left;  // Only goes one level!
    }
    // ...
}

// ✓ CORRECT - Push ALL left nodes
while (current != null || !stack.isEmpty()) {
    while (current != null) {  // Inner while loop!
        stack.push(current);
        current = current.left;
    }
    // ...
}

Mistake 3: Iterative - Wrong Stack Pop Order

// ❌ WRONG - Processes right before popping parent
while (!stack.isEmpty()) {
    TreeNode node = stack.peek();  // Peek instead of pop
    // ... process right first ...
}

// ✓ CORRECT - Pop then process
while (current != null || !stack.isEmpty()) {
    // Push left nodes...
    current = stack.pop();  // Pop to process!
    result.add(current.val);
    current = current.right;
}

Mistake 4: Modifying Tree During Traversal

// ❌ WRONG - Modifying tree while traversing
private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;

    inorder(node.left, result);
    result.add(node.val);
    node.val = 0;  // DON'T modify during traversal!
    inorder(node.right, result);
}

// ✓ CORRECT - Read-only traversal
private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;

    inorder(node.left, result);
    result.add(node.val);  // Just read!
    inorder(node.right, result);
}

🎯 Pattern Recognition - Traversal Applications

Core Pattern: DFS Traversal Orders

Template:
  void traverse(TreeNode node, List<Integer> result) {
      if (node == null) return;

      // Preorder: process here

      traverse(node.left, result);

      // Inorder: process here

      traverse(node.right, result);

      // Postorder: process here
  }

Position of processing determines order!

When to Use Each Traversal:

Inorder (Left → Root → Right): 

✓ BST: Get sorted order
✓ BST validation
✓ Finding kth smallest in BST
✓ BST iterator

Why? Left < Root < Right in BST!

Preorder (Root → Left → Right): 

✓ Copy tree structure
✓ Serialize tree
✓ Expression tree evaluation
✓ Create tree from traversal

Why? Process parent before children!

Postorder (Left → Right → Root): 

✓ Delete tree (cleanup)
✓ Calculate tree height
✓ Calculate directory size
✓ Dependency resolution

Why? Process children before parent!

1. Kth Smallest Element in BST 

Uses inorder traversal
BST property: inorder gives sorted order
Find kth element in inorder sequence

2. Validate Binary Search Tree 

Uses inorder traversal
Check if inorder is strictly increasing
If yes, valid BST

3. Binary Tree Preorder/Postorder Traversal 

Exact same pattern
Just change when you process node
Move result.add() line!

4. Serialize and Deserialize Binary Tree 

Uses preorder traversal
Rebuild tree from serialization
Preorder preserves structure

📝 Quick Revision Notes

🎯 Core Concept

Inorder = Left → Root → Right. Three ways: (1) Recursive (trivial - just follow order), (2) Iterative (use stack - simulate call stack), (3) Morris (O(1) space - skip for now). For BST, inorder gives sorted order! Position of result.add() determines traversal type: before recursion = preorder, between = inorder, after = postorder.

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static TreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0 || arr[0] == null) {
            return null;
        }

        TreeNode root = new TreeNode(arr[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while (!queue.isEmpty() && i < arr.length) {
            TreeNode current = queue.poll();

            // Process left child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.left = new TreeNode(arr[i]);
                    queue.offer(current.left);
                }
                i++;
            }

            // Process right child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.right = new TreeNode(arr[i]);
                    queue.offer(current.right);
                }
                i++;
            }
        }

        return root;
    }

    public static void print(TreeNode root) {
        if (root == null) {
            System.out.println("[]");
            return;
        }

        List<String> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                result.add(String.valueOf(node.val));
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                result.add("null");
            }
        }

        while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
            result.remove(result.size() - 1);
        }

        System.out.println(result);
    }    
}

class Solution {
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();

    // // Approach 1 - recursive DFS
    // recurisveDFS(root, res);

    // Approach 2 - iterative DFS (using stack)
    iterativeDFS(root, res);

    return res;
  }

  private void iterativeDFS(TreeNode root, List<Integer> res) {
    if(root == null) {
      return;
    }

    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
      // go left left left till the leaf node.
      while (curr != null) {
        stack.push(curr);
        curr = curr.left;
      }

      // Now we are at leaf node. Add to res.
      curr = stack.pop();
      res.add(curr.val);

      curr = curr.right;
    }
  }

  private void recurisveDFS(TreeNode root, List<Integer> res) {
    if(root == null) {
      return;
    }

    // inorder => left, root, right
    recurisveDFS(root.left, res);
    res.add(root.val);
    recurisveDFS(root.right, res);
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.inorderTraversal(TreeNode.buildTree(new Integer[] {1,null,2,3})));
    System.out.println(s.inorderTraversal(TreeNode.buildTree(new Integer[] {1,2,3,4,5,null,8,null,null,6,7,9})));
    System.out.println(s.inorderTraversal(TreeNode.buildTree(new Integer[] {})));
    System.out.println(s.inorderTraversal(TreeNode.buildTree(new Integer[] {1})));
  }
}

🔑 Key Insights

The Three Orders: 

INorder:   Left → IN (root) → Right    [4,2,5,1,3]
PREorder:  PRE (root) → Left → Right   [1,2,4,5,3]
POSTorder: Left → Right → POST (root)  [4,5,2,3,1]

Tree:      1
          / \
         2   3
        / \
       4   5

Just move where you process root!

Why Iterative Uses Stack: 

Recursion: Uses call stack (implicit)
Iterative: Uses Stack<TreeNode> (explicit)

Stack remembers:
  - Where we came from
  - What nodes to process next
  - Same as recursion, but manual!

BST Magic: 

BST Property: Left < Root < Right

Inorder traversal: Left → Root → Right

Result: Sorted order! ✨

This is why inorder is special for BST!

🎪 Memory Aid

"LEFT-IN-RIGHT for inorder!"
"Stack remembers the path!"
"BST inorder = sorted!"
"Three orders, one template!" ✨

⚠️ Don't Forget

  • Order matters (position of process determines type)
  • Stack simulates recursion (explicit vs implicit)
  • Inner while loop (push ALL left nodes in iterative)
  • Pop before process (don't peek in iterative)
  • BST inorder is sorted (important property!)
  • Result.add() placement (defines the traversal type)

🎉 Congratulations!

You've mastered tree traversal!

What You Learned:

✅ Three traversal orders - Inorder, Preorder, Postorder
✅ Recursive pattern - Simple and clean
✅ Iterative pattern - Stack simulation
✅ BST property - Inorder gives sorted order
✅ When to use each - Different applications
✅ Pattern template - Reusable for all three

The Foundation:

These traversals are FUNDAMENTAL!

You'll use them in:
  ✓ BST problems (inorder)
  ✓ Tree serialization (preorder)
  ✓ Tree deletion (postorder)
  ✓ Tree validation
  ✓ Path finding
  ✓ Expression evaluation

Master these, master trees! 🌳

Pattern Evolution:

Previous problems:
  ✓ Comparison (Same, Symmetric, Subtree)
  ✓ Calculation (Depth)
  ✓ Validation (Path Sum)
  ✓ Transformation (Invert)
  ✓ Collection (Paths)

Problem 139: Traversal
  ✓ Visit all nodes in specific ORDER
  ✓ Foundation for many algorithms
  ✓ Different orders for different uses

This is the CORE of tree algorithms!

Next Steps:

Perfect problems to apply traversals: - Preorder Traversal (same pattern!) - Postorder Traversal (same pattern!) - Kth Smallest in BST (uses inorder!) - Validate BST (uses inorder!)

You now have the traversal toolkit! 🧰🌳✨