Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

Constraints:

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

Follow up: Recursive solution is trivial, could you do it iteratively?

Approach: Iterative with an Explicit Stack

Algorithm

1. In inorder traversal, visit the left subtree, then the root, then the right subtree
2. Walk as far left as possible, pushing every node onto the stack
3. When no left child remains, pop a node, add its value to the result, and move to its right child
4. Repeat the walk-left, pop, move-right cycle until the stack is empty and the current node is null
5. The result is the nodes sorted by the inorder order

Time & Space Complexity

• Time Complexity: O(n) - every node is pushed and popped exactly once
• Space Complexity: O(h) - the stack holds at most the current path of depth h, O(n) in the worst case

Java Implementation

import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;

public class BinaryTreeInorderTraversal {

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            result.add(cur.val);
            cur = cur.right;
        }
        return result;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // Test method
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        System.out.println("Input: root = [1,null,2,3]");
        System.out.println("Output: " + inorderTraversal(root)); // Expected: [1, 3, 2]
    }
}

Recursive Implementation

public List<Integer> inorderTraversalRecursive(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    helper(root, result);
    return result;
}

private void helper(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    helper(node.left, result);
    result.add(node.val);
    helper(node.right, result);
}

Example Walkthrough

For root = [1, null, 2, 3]:

1. Push 1, then no left child. Pop 1 -> result [1], move to right child 2
2. Push 2, then push left child 3. No further left child, pop 3 -> result [1, 3]
3. 3 has no right child, pop 2 -> result [1, 3, 2]
4. 2 has no right child; stack empty and cur null, return [1, 3, 2]

Key Points

1. Left-Root-Right Order: The node value is added only after its whole left subtree has been visited
2. Two-Phase Loop: The inner loop descends left; the outer loop handles popping and moving right
3. BST Sortedness: For a binary search tree, inorder traversal produces values in ascending order
4. Iterative vs Recursive: The explicit stack replaces the recursion call stack
5. O(n) Time: Every node is visited exactly once