94. Binary Tree Inorder Traversal
You receive the root of a binary tree (each node has an integer value and optional left/right children). Visit every node in inorder — for any node, first everything in its left subtree, then the node itself, then everything in its right subtree — and return the values in the order you visit them.
Inorder is the traversal that reads a binary search tree's values in sorted order, which is why it shows up constantly.
The recursive version is three lines. The classic follow-ups: do it iteratively with an explicit stack, and then — the showpiece — with O(1) extra space using Morris threading.
Example 1:
Input: root = [1, null, 2, 3]
Output: [1, 3, 2]
Explanation: Node 1 has no left child, so it is visited first; then its right subtree — node 2's left child 3 comes before 2.
Example 2:
Input: root = [4, 2, 6, 1, 3, 5, 7]
Output: [1, 2, 3, 4, 5, 6, 7]
Explanation: The tree is a balanced BST, so inorder produces its values in sorted order.
Constraints:
- 0 ≤ number of nodes ≤ 100
- -100 ≤ node value ≤ 100
Hints:
Recursion mirrors the definition exactly: recurse left, record the node, recurse right. Get this working first.
For the iterative version, the stack replays what recursion does implicitly: slide down the left spine pushing every node, then pop one, record it, and switch to its right child.
Morris traversal gets O(1) space by temporarily threading each left subtree's rightmost node back to its ancestor, so the walk can climb back up without a stack — every thread is removed on the second visit, leaving the tree unchanged.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, null, 2, 3]
Expected output: [1, 3, 2]