☕ DSA Java Articles

Topics › Binary Trees › Traversals

Inorder Traversal

Easy TUF ID 133 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return the values of its nodes in inorder. Inorder means that, for every node, you list everything in its left subtree first, then the node itself, then everything in its right subtree. The tree is an ordinary binary tree (not necessarily a search tree), it may be empty, and values may repeat.

Constraints (LeetCode 94): between 0 and 100 nodes, values in [-100, 100]. The Java file also runs a 5000-node chain and a 100000-node balanced tree, because the interesting differences between the approaches only show up on large or deep trees.

Example 1

        1
       / \
      2   3
     / \   \
    4   5   6
answer = [4, 2, 5, 1, 3, 6]

The left subtree of 1 (rooted at 2) produces 4, 2, 5; then comes 1; then the right subtree produces 3, 6.

Example 2

root = [1, null, 2, 3]      // 1 has a right child 2, and 2 has a left child 3
answer = [1, 3, 2]

1 has no left subtree, so it is listed first. Inside its right subtree, 3 is the left child of 2, so it comes before 2.

Why this order is worth knowing: in a binary search tree every value in the left subtree is smaller than the node and every value in the right subtree is larger, so inorder lists a BST in sorted order. Many BST problems (validation, k-th smallest, fixing swapped nodes) are an inorder traversal with a small twist.

Approach 1: Recursion

Intuition. The definition of inorder is itself recursive: “inorder of a tree = inorder of the left subtree, then the root, then inorder of the right subtree”. A recursive method can be written straight from that sentence. The call stack does the bookkeeping for us: when the call for node X descends into X.left, the frame for X stays suspended, and when the left call returns, execution resumes exactly at “add X, then go right”.

Algorithm.

  1. If the node is null, return; an empty subtree contributes nothing.
  2. Recurse into the left child.
  3. Append the node’s value.
  4. Recurse into the right child.
static List<Integer> recursive(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    inorder(root, out);
    return out;
}

static void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    inorder(node.left, out);       // 1. everything smaller in a BST, everything "before" in general
    out.add(node.val);             // 2. the node itself
    inorder(node.right, out);      // 3. everything after
}

Complexity. Time O(n): every node is entered exactly once, and so is each of the n + 1 null children, which is still linear. Space O(h) for the call stack, where h is the height of the tree: O(log n) for a balanced tree, O(n) for a chain. The output list is not counted, because it is the answer itself.

The weak point is that h. Java’s default thread stack (typically 512 KB to 1 MB) runs out somewhere in the tens of thousands of frames, so a degenerate tree with 10^5 nodes on one path can throw StackOverflowError. That is the practical reason to know the iterative version.

Approach 2: Iterative with an explicit stack

Intuition. Look at what the recursion really does. Standing at a node, it immediately goes left and leaves the node “pending”: the node may only be emitted after its whole left subtree is done. So the first node ever emitted is the end of the left spine, the path obtained by following left pointers from the root.

We can imitate this with our own stack:

The stack therefore always holds exactly the ancestors whose left subtree is in progress, which is precisely the information the call stack held in Approach 1.

Algorithm.

  1. Set cur = root and start with an empty stack.
  2. While cur != null or the stack is not empty:
    • While cur != null: push cur, then cur = cur.left.
    • Pop the top node, append its value.
    • Set cur to that node’s right child.
  3. Return the list.
static List<Integer> iterative(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {          // push the whole left spine; each node waits for its left subtree
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();             // its left subtree is finished, so visit it
        out.add(cur.val);
        cur = cur.right;               // then traverse its right subtree the same way
    }
    return out;
}

Dry run on Example 1:

step pushed popped output so far cur after the step
1 1, 2, 4 4 4 null (4 has no right child)
2 (none) 2 4, 2 5
3 5 5 4, 2, 5 null
4 (none) 1 4, 2, 5, 1 3
5 3 3 4, 2, 5, 1, 3 6
6 6 6 4, 2, 5, 1, 3, 6 null, stack empty, stop

Complexity. Time O(n): every node is pushed once and popped once, and the inner loop’s total work across the whole run is exactly those n pushes. Space O(h): the stack only ever holds one root-to-node path. The asymptotic cost is the same as recursion, but the stack lives on the heap, so a deep chain no longer threatens a StackOverflowError.

If even O(h) extra memory is too much, Morris traversal reaches O(1) extra space by temporarily threading the tree; it is covered in its own article linked below.

Edge cases and pitfalls