94. Binary Tree Inorder Traversal
easyReturn the inorder traversal of a binary tree's node values. Recursion is one line; the iterative version with an explicit stack is the real interview test. Bonus points for Morris traversal in O(1) space.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder means left subtree, then node, then right subtree.
Constraints
The number of nodes in the tree is in the range [0, 100].-100 <= Node.val <= 100
Examples
Example 1
root = [1,null,2,3][1,3,2]Example 2
root = [][]Example 3
root = [1][1]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Recursion is trivial: traverse(left), append node.val, traverse(right).
Hint 2
Iterative version: use a stack. Push all left children, pop and visit, then move to right.
Hint 3
Morris traversal achieves O(1) space by temporarily rewiring rightmost predecessors as threads, then restoring.
Solution approach
Reveal approach
Iterative with explicit stack: initialize stack = [] and curr = root and result = []. Loop while curr is not null or stack is non-empty: while curr is not null, push curr and move curr = curr.left (drain the left spine). Then pop the top, append its val to result, and set curr = popped.right. Return result. The stack holds the ancestor chain of the next node to visit. Recursive variant is straightforward. Morris traversal does it in O(1) extra space by making the rightmost node of each left subtree point back to its inorder successor temporarily.
Complexity
- Time
- O(n)
- Space
- O(h)
Related patterns
- tree-dfs
- stack
- recursion
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Bloomberg
More Trees practice problems
- 98. Validate Binary Search Tree
- 100. Same Tree
- 101. Symmetric Tree
- 102. Binary Tree Level Order Traversal
- 103. Binary Tree Zigzag Level Order Traversal
- 104. Maximum Depth of Binary Tree
- 105. Construct Binary Tree from Preorder and Inorder Traversal
- 108. Convert Sorted Array to Binary Search Tree