Binary Tree Inorder Traversal — Practice

Problem

Given the root of a binary tree, return the inorder traversal of its nodes' values (left, node, right).

Examples

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].

Constraints

•The number of nodes is in the range [0, 100]
•-100 <= Node.val <= 100

Hints

Hint 1

The recursive version is nearly a direct transcription of the definition — the challenge is the iterative version.

Hint 2

An explicit stack can simulate the recursion: push left children as far as possible, then process and move right.

Hint 3

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.

Solutions

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