Given the root of a binary tree, return the inorder traversal of its nodes' values (left, node, right).
Example 1
Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation: Inorder: left subtree (empty), root (1)... actually traversal visits 1, then descends right to 2, then left to 3: result [1,3,2].
The number of nodes is in the range [0, 100]-100 <= Node.val <= 100The recursive version is nearly a direct transcription of the definition — the challenge is the iterative version.
An explicit stack can simulate the recursion: push left children as far as possible, then process and move right.
This exact pattern — push-left-chain, pop-and-process, move-right — reappears any time you need to convert a recursive tree traversal to iterative under time pressure.
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(TreeNode node, List<Integer> result) {
if (node == null) return;
inorder(node.left, result);
result.add(node.val);
inorder(node.right, result);
}Time: O(n) · Space: O(h) for the call stack, h = tree height