Log inSign up
easyleetcodeNot Started

Binary Tree Inorder Traversal

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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

In inorder traversal, nodes are visited in the order: Left -> Root -> Right.

Example 1 · Example 1: Standard Tree:

Input: root = [1, null, 2, 3]
Output: [1, 3, 2]
Explanation: Root 1 has no left child, so 1 is visited. Right subtree at 2 has left child 3, so 3 is visited before 2.

Example 2 · Example 2: Empty Tree:

Input: root = []
Output: []
Explanation: No nodes in tree.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Left -> Root -> Right recursive sequence.
  • Implement the classic push-all-left iterative stack pattern.
  • Understand Morris Inorder threading and traversal.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sorted sequence extraction from BST.
  • Left-to-right projection of tree nodes.
  • Inorder traversal.

Algorithmic Decision Tree:

  • Recursive: dfs(node.left), visit(node.val), dfs(node.right).
  • Iterative Stack: while curr || !stack.empty(): push all left, pop, visit, curr = node.right.
  • Morris: visit curr when pred.right == curr (second pass).

Connected Patterns:

Binary Tree Preorder TraversalBinary Tree Postorder TraversalValidate Binary Search Tree

1. Recursive DFS Inorder Traversal

Intuition

Recursively traverse left subtree, append current node value to result, then recursively traverse right subtree.

When to apply: Default standard implementation in most coding problems.

Algorithm

  1. Step 1: If root is null, return.
  2. Step 2: Recursively call dfs(root.left).
  3. Step 3: Append root.val to result.
  4. Step 4: Recursively call dfs(root.right).
  5. Step 5: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* root, vector<int>& ans) {
10 if (!root) return;
11 dfs(root->left, ans);
12 ans.push_back(root->val);
13 dfs(root->right, ans);
14 }
15 vector<int> inorderTraversal(TreeNode* root) {
16 vector<int> ans;
17 dfs(root, ans);
18 return ans;
19 }
20};
21
22int main() {
23 // Sample driver execution
24 cout << "Execution completed successfully." << endl;
25 return 0;
26}
27

Time & Space Complexity

  • Time complexity: O(n) — Visits each node once in O(n) time.
  • Space complexity: O(h) — Call stack takes O(h) space.

2. Iterative Stack Traversal (Push All Left)

Intuition

Keep a pointer curr = root. Loop while curr != null or stack is not empty. While curr != null, push curr to stack and curr = curr.left. When curr is null, pop node from stack, record node.val, and set curr = node.right.

When to apply: When avoiding recursion stack overflow.

Algorithm

  1. Step 1: curr = root, stack = empty.
  2. Step 2: While curr != null or stack is non-empty:
  3. - While curr != null: push curr, curr = curr.left.
  4. - Pop node from stack, add node.val to result.
  5. - curr = node.right.
  6. Step 3: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> inorderTraversal(TreeNode* root) {
10 vector<int> ans;
11 stack<TreeNode*> st;
12 TreeNode* curr = root;
13 while (curr || !st.empty()) {
14 while (curr) {
15 st.push(curr);
16 curr = curr->left;
17 }
18 curr = st.top();
19 st.pop();
20 ans.push_back(curr->val);
21 curr = curr->right;
22 }
23 return ans;
24 }
25};
26
27int main() {
28 // Sample driver execution
29 cout << "Execution completed successfully." << endl;
30 return 0;
31}
32

Time & Space Complexity

  • Time complexity: O(n) — Each node is pushed and popped exactly once.
  • Space complexity: O(h) — Stack depth equals tree height O(h).

3. Morris Inorder Traversal (Threaded Binary Tree)

Intuition

While curr is not null: if curr.left is null, record curr.val and curr = curr.right. Else find predecessor (pred = curr.left, move right until pred.right == null or pred.right == curr). If pred.right == null, set pred.right = curr and curr = curr.left. If pred.right == curr, cut thread pred.right = null, record curr.val (visit in inorder!), and curr = curr.right.

When to apply: When strictly O(1) auxiliary space is required.

Algorithm

  1. Step 1: curr = root.
  2. Step 2: While curr != null:
  3. - If curr.left == null: add curr.val, curr = curr.right.
  4. - Else:
  5. * pred = curr.left, while pred.right != null && pred.right != curr: pred = pred.right.
  6. * If pred.right == null: pred.right = curr, curr = curr.left.
  7. * Else: pred.right = null, add curr.val (inorder visit!), curr = curr.right.
  8. Step 3: Return result.

Inorder Trace for root = [1, 2, 3]

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Start at root (1), traverse left to node 2
Visual state
Values and pointers at this exact step
tree
Root
1
Left
2
Right
3

Node order shown; add connections to display explicit tree edges.

curr: 2
Check / comparison
Visit left child 2
Decision / next transition
Add 2 to output. Backtrack to root.
Why this step matters

Step 1: Start at root (1), traverse left to node 2. Node 2 has no left child, visit 2: [2].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> inorderTraversal(TreeNode* root) {
10 vector<int> ans;
11 TreeNode* curr = root;
12 while (curr) {
13 if (!curr->left) {
14 ans.push_back(curr->val);
15 curr = curr->right;
16 } else {
17 TreeNode* pred = curr->left;
18 while (pred->right && pred->right != curr) {
19 pred = pred->right;
20 }
21 if (!pred->right) {
22 pred->right = curr;
23 curr = curr->left;
24 } else {
25 pred->right = nullptr;
26 ans.push_back(curr->val); // visit on 2nd arrival
27 curr = curr->right;
28 }
29 }
30 }
31 return ans;
32 }
33};
34
35int main() {
36 // Sample driver execution
37 cout << "Execution completed successfully." << endl;
38 return 0;
39}
40

Time & Space Complexity

  • Time complexity: O(n) — Each edge is traversed at most 3 times, giving O(n) total time.
  • Space complexity: O(1) — Zero auxiliary memory beyond result container.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive DFSO(n)O(h)Natural call stack recursion: dfs(left), visit, dfs(right).Call stack depth.
2.Iterative StackO(n)O(h)Explicit stack pushing left spine, popping, moving right.Stack memory.
3.Morris InorderOptimalO(n)O(1)Temporary predecessor threading.None. Space optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root = [] -> returns [].
  • Single node tree: root = [1] -> returns [1].
  • Skewed left or right trees.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that Inorder traversal of a BST yields elements in strictly increasing order.
  2. Walk through the iterative stack loop condition: while (curr != null || !stack.isEmpty()).
  3. Explain the key difference in Morris Inorder vs Preorder: Inorder prints on the 2nd visit when cutting the thread.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When applied to a Binary Search Tree (BST), what property does the inorder traversal satisfy?

Back to DSA Sheet