Java binary-tree traversal: iterative inorder

Java 8+. Use a JDK that supports this release.

Store the suspended path

The explicit stack stores ancestors whose left subtree is being visited. Once no left child remains, pop the next node, consume it, and move into its right subtree. That replaces the suspended recursive frames with visible data.

The program constructs a search tree of depot IDs and prints inorder output. The traversal itself does not verify the search-tree invariant. Moving a larger ID into the left branch would produce a different order without causing an algorithm error.

A null root represents an empty tree. The loop exits immediately. Shared nodes or cycles are not part of this tree contract; a graph requires visited-state tracking.

Height controls the workspace

A balanced tree has a short root-to-leaf path. A chain-shaped tree can be as tall as its node count. The explicit stack handles that case without recursive Java calls, but it can still require linear storage.

Traversal does not balance the tree or speed up future searches. Insertion rules and rebalancing algorithms belong to separate lessons. This implementation teaches visitation order only.

Working program

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

public class DepotTree {
    static final class Node {
        final int depotId;
        Node left, right;
        Node(int depotId) { this.depotId = depotId; }
    }
    static List<Integer> inorder(Node root) {
        List<Integer> ordered = new ArrayList<>();
        Deque<Node> pending = new ArrayDeque<>();
        Node current = root;
        while (current != null || !pending.isEmpty()) {
            while (current != null) { pending.push(current); current = current.left; }
            current = pending.pop();
            ordered.add(current.depotId);
            current = current.right;
        }
        return ordered;
    }
    public static void main(String[] args) {
        Node root = new Node(40);
        root.left = new Node(20); root.right = new Node(60);
        root.left.right = new Node(30);
        System.out.println(inorder(root));
        System.out.println(inorder(null));
    }
}

Output

[20, 30, 40, 60]
[]

Cost and design choices

Every node is pushed and popped once, so traversal takes O(n) work. The pending stack takes O(h) references for height h. Returning all IDs also requires O(n) result storage; do not omit that from the total allocation estimate.

A consumer callback could avoid storing the whole result, but it would add failure and side-effect contracts. Decide whether partial output is acceptable before switching representations.

Common Mistakes

• Do not claim inorder sorts an arbitrary binary tree.
• Do not include null in an ArrayDeque.
• Do not assume every tree has logarithmic height.

Connect the contracts

Compare recursive traversal with call-stack depth before accepting an unbounded input tree.

Traversal order alone does not establish search-tree ordering.

Compare the boundary explained in Ordered search with the assumptions made by this program.