Given the root of a binary tree, return the inorder traversal of its values: left subtree → node → right subtree. Follow-up: do it iteratively instead of recursively.
root = [1,null,2,3][1,3,2]root = [1,2,3,4,5,null,8,null,null,6,7,9][4,2,6,5,7,1,3,9,8]1,null,2,3 · up to 15 nodescurr isn't null: push it 📚 and go leftRecursive inorder is go(left); visit(node); go(right). The stack stores exactly the nodes whose go(left) call is still running. Each node is pushed once and popped once, so the whole traversal is O(n). Bonus: on a BST, inorder gives the values in sorted order, which is behind "Validate BST" (98) and "Kth Smallest" (230).
Empty tree → [] (the loop never runs). Left-skewed tree → stack grows to n, so worst-case space is O(n). Loop condition must be curr != null || !stack.isEmpty(): either one alone stops too early. Morris traversal gets O(1) extra space by temporarily threading right pointers.
The recursive version is only three lines, but the interviewer often asks for the iterative one. The iterative version uses an explicit stack in place of the call stack.
Start at the root, and keep going left, pushing every node on the stack. When you cannot go left any more, pop the top node and record it. Then move to its right child, and repeat the same process from there. Stop when the current node is null and the stack is empty.
Go left as far as you can, pop, record, then go right. Inorder of a binary search tree is sorted.
Run the animation above on your own input, or watch the 1:57 video explanation of Binary Tree Inorder Traversal with a dry run and Java code.