Interview preparation
Binary Tree Inorder Traversal
1Problem statement
Given the root of a binary tree, return the inorder traversal (left, node, right) of its values. Follow-up: can you do it iteratively?
2Examples
3Constraints
- 0 ≤ number of nodes ≤ 100
- −100 ≤ Node.val ≤ 100
4Approaches
Approach 1
Brute Force: Recursion
inorder(left), visit node, inorder(right).
Approach 2
Better: Iterative with a stack
Push all left children, pop and visit, then move to the right child.
Approach 3
Optimal (space): Morris traversal
Temporarily thread the tree to walk it without a stack.
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
function inorderTraversal(root) {
const result = [];
const stack = [];
let node = root;
while (node !== null || stack.length > 0) {
while (node !== null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
result.push(node.val);
node = node.right;
}
return result;
}
function buildTree(values) {
if (values.length === 0 || values[0] === null) return null;
const root = new TreeNode(values[0]);
const queue = [root];
let i = 1;
while (queue.length > 0 && i < values.length) {
const node = queue.shift();
if (i < values.length && values[i] !== null) queue.push((node.left = new TreeNode(values[i])));
i++;
if (i < values.length && values[i] !== null) queue.push((node.right = new TreeNode(values[i])));
i++;
}
return root;
}
console.log(inorderTraversal(buildTree([1, null, 2, 3])));
console.log(inorderTraversal(buildTree([4, 2, 6, 1, 3, 5, 7])));
6Complexity
Time
O(n)
Space
O(h)
7Visual walkthrough
Related visualization (Binary Tree Inorder Traversal) — shows the core data-structure operations this solution relies on:
Recursively visits the left subtree, then the node itself, then the right subtree (Left → Root → Right). On a Binary Search Tree this produces the values in sorted order.