LeetCode 94. Binary Tree Inorder Traversal

Problem

Approach

An inorder traversal visits each node in left-node-right order. An explicit stack stores nodes whose left subtrees have not yet been fully processed. Starting at the root, descend as far left as possible and push each node. Then pop the next node, append its value, and move to its right child; repeat until both the current node and the stack are empty. This also returns an empty list when the root is null.

The stack contains at most one root-to-leaf path, so the auxiliary space is O(H), where H is the tree height. Every node is pushed and popped once, giving O(N) time. The traversal only reads the tree and does not mutate any node.

Java

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }

        return result;
    }
}