Binary Tree Inorder Traversal — Problem & Solution
Binary Tree Inorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Binary Tree Inorder Traversal is an easy coding problem on depth-first search, trees and stack, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees, Stack
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return the values of its nodes in inorder: for every node, first everything in its left subtree, then the node itself, then everything in its right subtree.
Example 1
Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation: Node 1 has no left child, so it comes first; then its right subtree, where 3 (the left child of 2) precedes 2.
Example 2
Input: root = [4,2,6,1,3,5,7]
Output: [1,2,3,4,5,6,7]
Explanation: This tree is a binary search tree, and an inorder walk of a BST always lists its values in sorted order.
Example 3
Input: root = []
Output: []
Constraints
The number of nodes in the tree is in the range [0, 100]-100 <= Node.val <= 100
Follow-up: The recursive walk is short — can you do it iteratively with an explicit stack?
Hints for Binary Tree Inorder Traversal
Hint 1
Inorder is a rule you apply at every node: left subtree, the node, right subtree.
Hint 2
A recursive helper that appends to one shared list follows that rule directly; the base case is an empty subtree.
Hint 3
Iteratively: push nodes while walking left; when you fall off, pop a node, record it, and continue from its right child.
How to solve Binary Tree Inorder Traversal
Inorder is defined recursively — left subtree, node, right subtree — so a depth-first walk that records each node between its two recursive calls produces the order exactly. An explicit stack does the same work without recursion.
Approach
- Start with an empty result list and an empty stack; set
cur = root. - While
curis not null, push it and move tocur.left. - When
curis null and the stack is not empty, pop a node, append its value, and setcurto its right child. - Stop when both
curis null and the stack is empty.
Why it works
A node is popped only after its entire left chain — and so its entire left subtree — has been pushed and popped, and its right subtree is started only after it has been recorded. That is precisely the inorder rule applied at every node.
Complexity
- Time —
O(n) — every node is pushed and popped once - Space —
O(h) for the stack (or the recursion), where h is the tree's height — O(n) for a chain
Pitfalls
- An empty tree returns an empty list, not an error.
- Recording the node before descending left gives preorder, not inorder.
- A tree that is a long left chain makes the stack as tall as the tree.
Reference solution
Python
from typing import List, Optional
def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
out = []
stack = []
cur = root
while cur is not None or stack:
while cur is not None:
stack.append(cur)
cur = cur.left
cur = stack.pop()
out.append(cur.val)
cur = cur.right
return outJava
public static int[] inorderTraversal(TreeNode root) {
List<Integer> out = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
out.add(cur.val);
cur = cur.right;
}
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> inorderTraversal(TreeNode* root) {
vector<int> out;
vector<TreeNode*> stack;
TreeNode* cur = root;
while (cur || !stack.empty()) {
while (cur) {
stack.push_back(cur);
cur = cur->left;
}
cur = stack.back();
stack.pop_back();
out.push_back(cur->val);
cur = cur->right;
}
return out;
}JavaScript
var inorderTraversal = function(root) {
var out = [], stack = [], cur = root;
while (cur !== null || stack.length > 0) {
while (cur !== null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
out.push(cur.val);
cur = cur.right;
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals