Given the root of a binary tree, return the values of its nodes in inorder: left subtree, node, right subtree.
Before you code
The recursive version is three lines. The real exercise is the iterative one, which must remember, for each node on the way down, that it still has to be visited after its left subtree.
Hints
- Iterative: start at the root; while the current node exists, push it and go left.
- When you can't go left, pop a node, record it, and move to its right child.
- Stop when the stack is empty and there is no current node.
- Compare the stack's maximum size with the tree's height.
Production & complexity notes
When solving Binary tree inorder traversal on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Vocabulary and traversals to reinforce the underlying pattern.
What it practices
Turning a recursive traversal into a loop with a stack, from Vocabulary and traversals.