DSA problem
Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder means visiting the left subtree first, then the current node, and finally the right subtree — a left-node-right ordering that is the foundation of nearly every BST algorithm.
The recursive definition is elegant and almost matches the English description verbatim: traverse the left subtree, record the current value, then traverse the right subtree. It costs O(n) time and O(h) call-stack space, where h is the height of the tree. For a balanced tree h is O(log n), but for a skewed tree h degenerates to O(n), which can overflow the call stack on deep inputs.
The iterative version makes that stack explicit using an array-backed stack. Starting from the root, we walk left as far as possible, pushing each node onto the stack. When we cannot go left anymore, we pop a node, record its value, and switch to its right child — repeating the same left-walk from there. This simulates exactly what recursion would do and is the canonical interview answer because it avoids hidden recursion depth limits.
A more advanced O(1)-space option is Morris traversal, which temporarily rewires right pointers of the rightmost predecessors to create a thread back to the root, then restores them. It is interesting but rarely required — the iterative-with-stack approach is what most interviewers expect and what we showcase here as canonical.
Examples
root = [1,null,2,3][1,3,2]root = [][]root = [1,2,3,4,5,6,7][4,2,5,1,6,3,7]Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
- Could you do it iteratively? (Follow-up that the canonical answer addresses.)
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.