Binary Tree Traversals in Java: Inorder, Preorder, Postorder and Level Order (Recursive and Iterative)

Versions this was built and run against. JDK 25.0.5+8 (Temurin, LTS), JUnit 6.1.3 (latest GA on Maven Central, and the version the sibling modules use), Maven 3.9.11. No other library: only java.util. Everything quoted below comes from a committed file in the binary-tree-traversals module of the java-interview-lab repository, and the 15 tests there pass. The stack-overflow depths are measurements from one shared 2-core sandbox; the page says where that matters.

A traversal visits every node once, in a chosen order

public final class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

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

The one idea behind the three depth-first orders

The name is the position of the root. Pre = root before the subtrees. In = root between them. Post = root after them. If you can reproduce the diagram above on a blank page you can derive any of the three on the spot, and you do not need to memorise “NLR, LNR, LRN” as three separate facts.

Recursive traversals: three methods, one line moved

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

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

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

recursive inorder        : [4, 2, 7, 5, 1, 3, 8, 6, 9]
recursive preorder       : [1, 2, 4, 5, 7, 3, 6, 8, 9]
recursive postorder      : [4, 7, 5, 2, 8, 9, 6, 3, 1]

Now the same lists as numbers on the tree. In each picture the amber badge is the position at which that node is written, so the badge sequence 1, 2, 3, … is the output read left to right.

inserted in this order : [50, 30, 70, 20, 40, 60, 80]
tree                   : 50(30(20,40),70(60,80))
inorder                : [20, 30, 40, 50, 60, 70, 80]

This only holds for a search tree. The sample tree is a plain binary tree, so its inorder list 4 2 7 5 1 3 8 6 9 is not sorted. “Inorder is sorted” is a property of the BST ordering rule, not of inorder traversal itself, and exam questions are written to catch exactly that confusion.

Going deeper

• Tail recursion does not help here, because the recursive call is not the last thing the method does: Tail vs Non-Tail Recursion in Java.

Where recursion breaks: a tree one million levels deep

private static void probe(TreeNode node, int depth) {
    if (node == null) {
        return;
    }
    if (depth > deepestEntered) {
        deepestEntered = depth;
    }
    probe(node.left, depth + 1);
    probe(node.right, depth + 1);
}

Depth reached by a recursive probe before StackOverflowError (3 attempts in one JVM):
  attempt 1: StackOverflowError after reaching depth 21258
  attempt 2: StackOverflowError after reaching depth 29514
  attempt 3: StackOverflowError after reaching depth 29514

RecursiveTraversals.inorder on the same tree:
  caught java.lang.StackOverflowError
  stack trace length: 1024 frames (the JVM truncates traces; the real depth is larger)
      at com.ankurm.interviewlab.bintree.RecursiveTraversals.inorder(RecursiveTraversals.java:20)
      at com.ankurm.interviewlab.bintree.RecursiveTraversals.inorder(RecursiveTraversals.java:20)
      at com.ankurm.interviewlab.bintree.RecursiveTraversals.inorder(RecursiveTraversals.java:20)
      at com.ankurm.interviewlab.bintree.RecursiveTraversals.inorder(RecursiveTraversals.java:20)
      ...

IterativeTraversals.inorder on the same tree:
  visited 1000000 nodes, first=1000000, last=1, no error

Do not quote these depths as “the limit”. They are machine, JVM-build and run dependent, and they even differ between attempts inside one JVM: attempt 1 managed 21,258 on the default stack and attempt 3 managed 29,514, because the JIT compiler replaces the large interpreter frames with smaller compiled ones as the method gets hot. The honest statement is the shape: depth scales roughly with stack size, it is in the tens of thousands for a default stack, and a tree whose height is controlled by user data can exceed it.

Going deeper

• StackOverflowError, Java SE 25 API.
• Raising -Xss only moves the cliff. It also multiplies memory per thread, so it is a poor fix for a service that runs thousands of threads.
• Self-balancing trees (AVL, red-black) keep the height near log n, which is why TreeMap never has this problem; see Mastering TreeSet in Java.

Iterative inorder: let the stack remember the way back

public static List<Integer> inorder(TreeNode root, StepListener listener) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {          // go as far left as possible, remembering the way back
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();             // nothing further left: this node is next
        out.add(current.val);
        current = current.right;           // then the whole right subtree
    }
    return out;
}

The fingerprint of a wrong iterative inorder: the loop condition while (!stack.isEmpty()) alone. It exits immediately on the first iteration, because the stack starts empty and the root has not been pushed yet. The correct condition is current != null || !stack.isEmpty(): keep going while there is a node to descend into or a node waiting to be written.

Iterative preorder: push the right child first

public static List<Integer> preorder(TreeNode root, StepListener listener) {
    List<Integer> out = new ArrayList<>();
    if (root == null) {
        return out;
    }
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.add(node.val);
        if (node.right != null) {
            stack.push(node.right);        // pushed first so it is popped last
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return out;
}

Iterative postorder: the hard one, two ways

public static List<Integer> postorderTwoStacks(TreeNode root, StepListener listener) {
    List<Integer> out = new ArrayList<>();
    if (root == null) {
        return out;
    }
    Deque<TreeNode> first = new ArrayDeque<>();
    Deque<TreeNode> second = new ArrayDeque<>();
    first.push(root);
    while (!first.isEmpty()) {             // phase 1: root-right-left order lands on `second`
        TreeNode node = first.pop();
        second.push(node);
        if (node.left != null) {
            first.push(node.left);
        }
        if (node.right != null) {
            first.push(node.right);
        }
    }
    while (!second.isEmpty()) {            // phase 2: popping reverses it into left-right-root
        TreeNode node = second.pop();
        out.add(node.val);
    }
    return out;
}

public static List<Integer> postorderOneStack(TreeNode root, StepListener listener) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    TreeNode lastVisited = null;           // the node we most recently wrote to the output
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        TreeNode top = stack.peek();
        if (top.right != null && top.right != lastVisited) {
            current = top.right;           // right subtree still unvisited
        } else {
            stack.pop();                   // both children finished (or absent)
            out.add(top.val);
            lastVisited = top;
        }
    }
    return out;
}

public static List<Integer> morrisInorder(TreeNode root, StepListener listener) {
    List<Integer> out = new ArrayList<>();
    List<Integer> threads = new ArrayList<>();
    TreeNode current = root;
    while (current != null) {
        if (current.left == null) {
            out.add(current.val);
            current = current.right;
        } else {
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }
            if (predecessor.right == null) {
                predecessor.right = current;   // create the thread
                threads.add(predecessor.val);
                current = current.left;
            } else {
                predecessor.right = null;      // thread found: left side finished, remove it
                threads.remove(Integer.valueOf(predecessor.val));
                out.add(current.val);
                current = current.right;
            }
        }
    }
    return out;
}

Going deeper

• The sample-tree results of every variant, side by side: output/01-sample-tree-all-traversals.txt.
• Morris preorder is the same loop but writes the node the first time it is reached, when the thread is created: morrisPreorder in the same file.
• Original paper: J. M. Morris, “Traversing binary trees simply and cheaply”, Information Processing Letters 9(5), 1979.

Level order: swap the stack for a queue

public static List<Integer> levelOrder(TreeNode root, StepListener listener) {
    List<Integer> out = new ArrayList<>();
    if (root == null) {
        return out;
    }
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        out.add(node.val);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    return out;
}

public static List<List<Integer>> byLevel(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) {
        return levels;
    }
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int sizeOfThisLevel = queue.size();
        List<Integer> level = new ArrayList<>(sizeOfThisLevel);
        for (int i = 0; i < sizeOfThisLevel; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        levels.add(level);
    }
    return levels;
}

public static List<List<Integer>> zigzag(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) {
        return levels;
    }
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    boolean leftToRight = true;
    while (!queue.isEmpty()) {
        int sizeOfThisLevel = queue.size();
        Deque<Integer> level = new ArrayDeque<>();
        for (int i = 0; i < sizeOfThisLevel; i++) {
            TreeNode node = queue.poll();
            if (leftToRight) {
                level.addLast(node.val);
            } else {
                level.addFirst(node.val);
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        levels.add(new ArrayList<>(level));
        leftToRight = !leftToRight;
    }
    return levels;
}

level order (queue)       : [1, 2, 3, 4, 5, 6, 7, 8, 9]
level order by level      : [[1], [2, 3], [4, 5, 6], [7, 8, 9]]
zigzag                    : [[1], [3, 2], [4, 5, 6], [9, 8, 7]]

Going deeper

• Use ArrayDeque, not LinkedList, as the queue: it is array-backed and faster in practice. ArrayDeque, Java SE 25 API. Queue basics: Java Implementation of Queue using Linked List.
• Level order is also the shortest-path algorithm for unweighted graphs; a tree is just a graph with no cycles.

Height and diameter: the O(n) answer and the O(n²) trap

public static int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(height(node.left), height(node.right));
}

nodes                         : 9
leaves                        : 4
height, counted in nodes      : 4
height, counted in edges      : 3
height via level order (BFS)  : 4
diameter, counted in nodes    : 7
diameter, counted in edges    : 6
one longest path              : [7, 5, 2, 1, 3, 6, 8]
height of the subtree at node : {1=4, 2=3, 3=3, 4=1, 5=2, 6=2, 7=1, 8=1, 9=1}

public static int diameterNaive(TreeNode node, long[] visits) {
    if (node == null) {
        return 0;
    }
    visits[0]++;
    int through = heightCounting(node.left, visits) + heightCounting(node.right, visits) + 1;
    int inLeft = diameterNaive(node.left, visits);
    int inRight = diameterNaive(node.right, visits);
    return Math.max(through, Math.max(inLeft, inRight));
}

private static int heightCounting(TreeNode node, long[] visits) {
    if (node == null) {
        return 0;
    }
    visits[0]++;
    return 1 + Math.max(heightCounting(node.left, visits), heightCounting(node.right, visits));
}

public static int diameterOnePass(TreeNode root, long[] visits) {
    int[] best = {0};
    heightAndDiameter(root, best, visits);
    return best[0];
}

private static int heightAndDiameter(TreeNode node, int[] best, long[] visits) {
    if (node == null) {
        return 0;
    }
    visits[0]++;
    int left = heightAndDiameter(node.left, best, visits);
    int right = heightAndDiameter(node.right, best, visits);
    best[0] = Math.max(best[0], left + right + 1);
    return 1 + Math.max(left, right);
}

tree                      nodes   naive visits     one-pass   diameter
sample (9)                    9             26            9          7
perfect, 4 levels            15             49           15          7
perfect, 7 levels           127            769          127         13
perfect, 10 levels         1023           9217         1023         19
left-skewed 100             100           5050          100        100
left-skewed 1000           1000         500500         1000       1000
left-skewed 2000           2000        2001000         2000       2000

Check the convention before you answer. The diameter of the sample tree is 7 if you count nodes and 6 if you count edges; its height is 4 nodes or 3 edges. LeetCode 543 (“Diameter of Binary Tree”) counts edges, so it expects 6 for this tree; many university papers count nodes. The algorithm is the same and the answer differs by one, so state which one you used.

Going deeper

• Height without recursion: the number of levels a queue traversal passes through, heightIterative in TreeMetrics.java. The tests check it against the recursive height on 1,000 random trees.
• The tests also check the diameter against an independent brute force (BFS from every node over the tree seen as an undirected graph), not only against the other implementation.

Rebuilding a tree from two traversals

private static TreeNode buildPre(int[] pre, int[] next, int lo, int hi, Map<Integer, Integer> position,
                                 Consumer<String> trace, int depth) {
    if (lo > hi) {
        return null;
    }
    int rootValue = pre[next[0]++];
    int mid = position.get(rootValue);
    TreeNode node = new TreeNode(rootValue);
    node.left = buildPre(pre, next, lo, mid - 1, position, trace, depth + 1);
    node.right = buildPre(pre, next, mid + 1, hi, position, trace, depth + 1);
    return node;
}

inorder   : [4, 2, 5, 1, 6, 3]
preorder  : [1, 2, 4, 5, 3, 6]
root 1  inorder slice [0..5]  left size 3, right size 2
  root 2  inorder slice [0..2]  left size 1, right size 1
    root 4  inorder slice [0..0]  left size 0, right size 0
    root 5  inorder slice [2..2]  left size 0, right size 0
  root 3  inorder slice [4..5]  left size 1, right size 0
    root 6  inorder slice [4..4]  left size 0, right size 0
result    : 1(2(4,5),3(6,-))
postorder of the result: [4, 5, 2, 6, 3, 1]

Preorder plus postorder is not enough. Inorder is what separates “left” from “right”. Without it, a node with a single child is ambiguous. The program (output/10-construct-from-traversals.txt) shows two different trees with identical preorder and identical postorder:

  1(2,-)  preorder [1, 2]  postorder [2, 1]
  1(-,2)  preorder [1, 2]  postorder [2, 1]

Complexity and which traversal to pick

void allDepthFirstImplementationsAgreeOnRandomTrees() {
    Random random = new Random(20261106L);
    for (int round = 0; round < 1000; round++) {
        int n = random.nextInt(80);
        TreeNode root = Trees.random(random, n);
        String shape = Trees.bracket(root);

        List<Integer> in = RecursiveTraversals.inorder(root);
        List<Integer> pre = RecursiveTraversals.preorder(root);
        List<Integer> post = RecursiveTraversals.postorder(root);
        assertEquals(n, in.size());

        assertEquals(in, IterativeTraversals.inorder(root), shape);
        assertEquals(pre, IterativeTraversals.preorder(root), shape);
        assertEquals(post, IterativeTraversals.postorderTwoStacks(root), shape);
        assertEquals(post, IterativeTraversals.postorderOneStack(root), shape);
        assertEquals(in, IterativeTraversals.morrisInorder(root), shape);
        assertEquals(shape, Trees.bracket(root), "Morris inorder must restore the tree");
        assertEquals(pre, IterativeTraversals.morrisPreorder(root), shape);
        assertEquals(shape, Trees.bracket(root), "Morris preorder must restore the tree");

        // construction round trips
        TreeNode a = Trees.fromInorderPreorder(Trees.toArray(in), Trees.toArray(pre), null);
        TreeNode b = Trees.fromInorderPostorder(Trees.toArray(in), Trees.toArray(post));
        assertEquals(shape, Trees.bracket(a));
        assertEquals(shape, Trees.bracket(b));
    }
}

Exam-style questions with answers

Should you hand-write these in production? Almost never. If you need a sorted structure, TreeMap and TreeSet are balanced red-black trees whose iterators already walk in inorder and cannot degenerate into the skewed chain from the overflow section. Hand-written traversals earn their place in interviews, in exams, and in the rare case of your own tree structure, such as a parser’s AST or a decision tree. For those, prefer the iterative stack versions when the depth depends on input you do not control, and keep recursion for trees you know are shallow. Morris is worth understanding and rarely worth shipping.

Further reading

• Companion code, tests and transcripts: java-interview-lab / binary-tree-traversals
• Implementing Binary Search Tree in Java
• Implementation of Stack in Java
• Java Implementation of Queue using Linked List
• Tail vs Non-Tail Recursion in Java
• Mastering TreeSet in Java
• LRU Cache in Java (another data-structure interview classic, same repository)
• Java Interview Preparation Guide
• Tree traversal (Wikipedia)
• ArrayDeque, Java SE 25 API
• StackOverflowError, Java SE 25 API
• Practice problems on LeetCode (search by number): 94 inorder, 144 preorder, 145 postorder, 102 level order, 103 zigzag, 104 maximum depth, 543 diameter, 105 construct from preorder and inorder.