Binary Tree Inorder Traversal
Problem Statement
Given the root of a binary tree, return the inorder traversal of its node values. In inorder traversal, visit the left subtree, then the current node, then the right subtree.
Input
The root pointer of a binary tree, or null for an empty tree.
Output
A list of integers in left, node, right order.
Constraints
- •
0 <= number of nodes <= 100 - •
-100 <= Node.val <= 100
Examples
Example 1
root = [1,null,2,3]
[1,3,2]Example 2
root = []
[]Learning Objectives
- Recognise inorder as the left, node, right DFS order.
- Explain that visiting means appending a node value only after its left subtree finishes.
- Convert the recursive call stack into an explicit stack.
- Connect inorder traversal with sorted output in a BST.
Intuition
Pattern Recognition
The signal is inorder traversal, left, root, right, or a BST task that needs values in sorted order. Visiting a node means appending its value to the answer list. In inorder, the visit is delayed until the left subtree has completely finished.
The common trap is appending the node too early. If the value is added before the left call, the traversal becomes preorder. In the iterative version, the stack stores ancestors while the traversal keeps walking left.
Common mistakes
- ×Appending before traversing the left subtree, which changes the order to preorder.
- ×Forgetting to move to the right child after popping a node from the stack.
- ×Pushing **null** into **ArrayDeque** instead of checking children first.
- ×Ignoring the O(h) recursion stack used by the recursive solution.
Algorithm Explanation
Key idea
Inorder treats every node as the middle of a three-part sequence: left subtree, node, right subtree. The recursive version writes those three actions directly. The iterative version simulates the same delayed visit by pushing nodes while moving left, then popping the next node whose left side is done.
Recursion walkthrough
Use [1,null,2,3]. Start at 1 and recurse left; that child is null, so return and visit 1, giving [1]. Move right to 2. Before 2 can be visited, recurse left to 3. Node 3 has no left child, so visit 3, giving [1,3]. Return to 2, visit it, and finish with [1,3,2]. The explicit stack mirrors the same pauses: push 1, pop and visit it, push 2, push 3, visit 3, then visit 2.
Algorithm
- For recursion, return on null.
- Recurse into node.left.
- Append node.val.
- Recurse into node.right.
- For iteration, push nodes while walking left.
- Pop one node, append it, then move to its right child.
- Stop when there is no current node and the stack is empty.
Solutions
Solution 1: Recursive inorder DFS
Use this when recursion is allowed. It is the clearest expression of left, node, right.
Run a helper that returns on null, recursively finishes the left subtree, appends the current value, then recursively finishes the right subtree.
Step-by-step
- Create an empty result list.
- Call dfs(root, result).
- If node is null, return.
- Recurse on node.left.
- Add node.val to the result.
- Recurse on node.right and return the list.
O(n)
O(h)
Every node is visited once; the recursion stack grows to tree height **h**, which is O(n) for a skewed tree.
Java implementation
Solution 2: Iterative inorder with explicit stack
Use this when recursion depth is a concern or the interviewer asks for a manual stack.
Walk left while pushing ancestors. When left is exhausted, pop the next ancestor, visit it, and then explore its right subtree.
Step-by-step
- Create an empty result list and stack.
- Set current to root.
- While current exists, push it and move left.
- Pop the stack when the left chain ends.
- Append the popped node value.
- Move current to the popped node right child and repeat.
O(n)
O(h)
Each node is pushed and popped once; the explicit stack holds a path of height **h**, O(n) in the worst case.
Java implementation
Dry Run
Sample input
root = [1,null,2,3]. Track the iterative stack; the top is shown on the right.
| step | current | action | stack | result |
|---|---|---|---|---|
| start | 1 | begin | [] | [] |
| 1 | 1 | push and move left | [1] | [] |
| 2 | null | pop and visit 1 | [] | [1] |
| 3 | 2 | push 2, then push 3 | [2,3] | [1] |
| 4 | null | pop and visit 3 | [2] | [1,3] |
| 5 | null | pop and visit 2 | [] | [1,3,2] |
A node is appended only after its left side has finished. That is why 3 appears before 2.
Interview Tips
State the order before coding: left, node, right. For BSTs, inorder streams values in sorted order, which leads directly to validation and kth-smallest follow-ups. If asked about O(1) auxiliary space, mention Morris traversal, which temporarily rewires predecessor links, but do not code it unless requested.
Likely follow-ups
- How does inorder traversal produce sorted values in a BST?
- Can you stop after the kth visited node?
- Can you write the traversal without recursion?
- What tradeoff does Morris traversal make to reach O(1) auxiliary space?
Similar Problems
Key Takeaways
- Inorder means **left, node, right**.
- The current node is visited after its left subtree completes.
- The explicit stack stores ancestors while the traversal walks left.
- Inorder is the traversal most closely tied to BST sorted order.