LogoKode$word

LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 94 Binary Tree Inorder Traversal using Recursive and Iterative approaches in Java. Includes tree traversal intuition, dry run, stack-based solution, complexity analysis, interview tips, and common mistakes.

Krishna Shrivastava
3 views
LinkedInGithubX
0
0
LeetCodeBinary Tree Inorder TraversalBinary TreeTree TraversalJavaDFSStackRecursionEasy
LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 94 – Binary Tree Inorder Traversal is one of the most important beginner-friendly tree problems in Data Structures and Algorithms.

This problem helps you understand:

  1. Binary tree traversal
  2. Depth First Search (DFS)
  3. Recursion
  4. Stack-based traversal
  5. Tree interview fundamentals

It is commonly asked in coding interviews because tree traversal forms the foundation of many advanced tree problems.

Problem Link

🔗 Problem

LeetCode 94: Binary Tree Inorder Traversal

Official Problem:

LeetCode Problem Link

Problem Statement

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

What is Inorder Traversal?

In inorder traversal, we visit nodes in this order:

Left → Root → Right

Example

Input

root = [1,null,2,3]

Tree Structure:

1
\
2
/
3

Inorder Traversal

Step-by-step:

1 → 3 → 2

Output:

[1,3,2]

Recursive Approach (Most Common)

Intuition

In inorder traversal:

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

This naturally fits recursion because trees themselves are recursive structures.

Recursive DFS Visualization

Traversal order:

Left → Node → Right

Recursive function:

inorder(node.left)
visit(node)
inorder(node.right)

Java Recursive Solution

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* }
*/

class Solution {

public void solve(List<Integer> list, TreeNode root) {

if(root == null) return;

solve(list, root.left);

list.add(root.val);

solve(list, root.right);
}

public List<Integer> inorderTraversal(TreeNode root) {

List<Integer> list = new ArrayList<>();

solve(list, root);

return list;
}
}

Dry Run – Recursive Approach

Tree:

1
\
2
/
3

Step 1

Start at:

1

Move left:

null

Return back.

Add:

1

Step 2

Move right to:

2

Move left to:

3

Add:

3

Return back.

Add:

2

Final Answer

[1,3,2]

Time Complexity – Recursive

Time Complexity

O(N)

Every node is visited once.

Space Complexity

O(H)

Where:

  1. H = height of tree
  2. Recursive call stack uses extra space

Worst case:

O(N)

for skewed trees.

Iterative Approach (Interview Follow-Up)

The follow-up asks:

Can you solve it iteratively?

Yes.

We use a stack to simulate recursion.

Iterative Inorder Intuition

The recursive order is:

Left → Node → Right

So iteratively:

  1. Keep pushing left nodes into stack
  2. Process current node
  3. Move to right subtree

Stack-Based Traversal Logic

Algorithm

While current node exists OR stack is not empty:

  1. Push all left nodes
  2. Pop top node
  3. Add node value
  4. Move to right subtree

Java Iterative Solution

class Solution {

public List<Integer> inorderTraversal(TreeNode root) {

List<Integer> ans = new ArrayList<>();

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

TreeNode curr = root;

while(curr != null || !stack.isEmpty()) {

while(curr != null) {
stack.push(curr);
curr = curr.left;
}

curr = stack.pop();

ans.add(curr.val);

curr = curr.right;
}

return ans;
}
}

Dry Run – Iterative Approach

Tree:

1
\
2
/
3

Step 1

Push:

1

Stack:

[1]

Step 2

Pop:

1

Add:

1

Move right to:

2

Step 3

Push:

2
3

Stack:

[2,3]

Step 4

Pop:

3

Add:

3

Step 5

Pop:

2

Add:

2

Final Answer

[1,3,2]

Comparison of Approaches

ApproachAdvantagesDisadvantages
RecursiveEasy to write and understandUses recursion stack
IterativeBetter interview practiceSlightly harder logic

Interview Explanation

In interviews, explain:

In inorder traversal, we process nodes in Left → Root → Right order. Recursion naturally fits this traversal. For iterative traversal, we use a stack to simulate recursive calls.

This demonstrates strong tree traversal understanding.

Common Mistakes

1. Wrong Traversal Order

Incorrect:

Root → Left → Right

That is preorder traversal.

Correct inorder:

Left → Root → Right

2. Forgetting Null Base Case

Always check:

if(root == null) return;

3. Stack Handling Errors

In iterative traversal:

  1. Push all left nodes first
  2. Then process node
  3. Then move right

FAQs

Q1. Why is inorder traversal important?

It is heavily used in:

  1. Binary Search Trees
  2. Expression trees
  3. Tree reconstruction problems

Q2. What is the inorder traversal of a BST?

It produces values in sorted order.

Q3. Which approach is better for interviews?

Recursive is easier.

Iterative is preferred for deeper interview rounds.

Q4. Can inorder traversal be done without stack or recursion?

Yes.

Using Morris Traversal with:

O(1)

space.

Bonus: Morris Traversal (Advanced)

Morris Traversal performs inorder traversal without recursion or stack.

Complexity

Time Complexity

O(N)

Space Complexity

O(1)

This is an advanced interview optimization.

Conclusion

LeetCode 94 is one of the most fundamental tree traversal problems.

It teaches:

  1. DFS traversal
  2. Recursion
  3. Stack simulation
  4. Binary tree fundamentals

The key inorder pattern is:

Left → Root → Right

Mastering this problem builds a strong foundation for advanced tree interview questions like:

  1. BST validation
  2. Tree iterators
  3. Tree reconstruction
  4. Morris traversal
  5. Kth smallest in BST

Related Articles

LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 144 Binary Tree Preorder Traversal using Recursive and Iterative approaches in Java. Includes traversal intuition, stack-based solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 145 Binary Tree Postorder Traversal using Recursive and Iterative approaches in Java. Includes traversal intuition, stack-based solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 102: Binary Tree Level Order Traversal – Java BFS Solution Explained

LeetCode 102: Binary Tree Level Order Traversal – Java BFS Solution Explained

Learn how to solve LeetCode 102 Binary Tree Level Order Traversal using BFS and Queue in Java. Includes brute force intuition, optimized level order traversal, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 1306: Jump Game III – Java DFS & Graph Traversal Solution Explained

LeetCode 1306: Jump Game III – Java DFS & Graph Traversal Solution Explained

Learn how to solve LeetCode 1306 Jump Game III using DFS and graph traversal in Java. Includes brute force intuition, optimized recursive solution, BFS approach, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
Ai Assistant Kas