☕ DSA Java Articles

Topics › Binary Trees › Traversals

Pre, Post, Inorder in one traversal

Easy TUF ID 136 A2ZSDE

Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, produce its preorder, inorder and postorder traversals, and do it in a single traversal of the tree rather than three separate ones. Return the three lists as [preorder, inorder, postorder]. (Some platforms ask for a different order of the three lists, such as [inorder, preorder, postorder]; reordering the result is trivial.) An empty tree gives three empty lists.

Constraints: between 0 and 10^5 nodes, arbitrary 32-bit values, duplicates allowed.

Trees are written in LeetCode’s level-order form, where null marks a missing child.

Example 1

          1
        /   \
       2     3
      / \   / \
     4   5 6   7
root = [1, 2, 3, 4, 5, 6, 7]
preorder  = [1, 2, 4, 5, 3, 6, 7]
inorder   = [4, 2, 5, 1, 6, 3, 7]
postorder = [4, 5, 2, 6, 7, 3, 1]

Example 2

    1
   /
  2
 /
3
root = [1, 2, null, 3]
preorder  = [1, 2, 3]
inorder   = [3, 2, 1]      // a left chain is read bottom-up in inorder
postorder = [3, 2, 1]

The key observation. Picture a depth-first walk tracing around the outline of the tree. It passes every node three times: once when it arrives from the parent, once when it comes back up from the left child, and once when it comes back up from the right child (a missing child counts as an instant round trip). The three classic traversals are nothing more than “record the node at its first, second, or third pass”:

So one walk that records on all three passes produces all three lists.

Approach 1: Brute force, three separate traversals

Intuition. Write the three standard recursive traversals and call each one. This is correct and still linear, but it walks the tree three times, which is exactly what the problem asks us to avoid.

static List<List<Integer>> threeTraversals(TreeNode root) {
    List<Integer> pre = new ArrayList<>(), in = new ArrayList<>(), post = new ArrayList<>();
    preorder(root, pre);
    inorder(root, in);
    postorder(root, post);
    return List.of(pre, in, post);
}

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);
}

Complexity. Time O(n), but with three full passes (3n node visits). Space O(h) for the recursion, where h is the height.

Approach 2: One recursive walk with three hooks

Intuition. In a recursive traversal the three passes over a node are three moments inside the same function call: before the first recursive call, between the two recursive calls, and after the second one. Put one add in each place.

Algorithm.

  1. If the node is null, return.
  2. Append the node to pre.
  3. Recurse into the left child.
  4. Append the node to in.
  5. Recurse into the right child.
  6. Append the node to post.
static List<List<Integer>> oneRecursion(TreeNode root) {
    List<Integer> pre = new ArrayList<>(), in = new ArrayList<>(), post = new ArrayList<>();
    walk(root, pre, in, post);
    return List.of(pre, in, post);
}

private static void walk(TreeNode node, List<Integer> pre, List<Integer> in, List<Integer> post) {
    if (node == null) return;
    pre.add(node.val);                        // 1st visit: arriving from the parent
    walk(node.left, pre, in, post);
    in.add(node.val);                         // 2nd visit: back from the left subtree
    walk(node.right, pre, in, post);
    post.add(node.val);                       // 3rd visit: back from the right subtree
}

Why it works. The pre.add calls happen in exactly the order a preorder traversal would make them, because deleting the other two add lines leaves the preorder function unchanged. The same argument applies to the other two lists. One walk, three subsequences of its events.

Complexity. Time O(n) with one pass. Space O(h) for the call stack, which is O(n) on a chain and can overflow Java’s default stack for very deep trees.

Approach 3: One stack of (node, state) frames

Intuition. Make the recursion explicit. Each stack frame stores a node and a state that says which pass comes next, mirroring where a suspended recursive call would resume:

We only peek at the top frame and change its state in place; a frame is popped only when it reaches state 3. Some write-ups pop the frame every time and push it back with the state incremented. That is equivalent, just with more stack traffic.

static class Frame {
    TreeNode node;
    int state = 1;                            // 1 = pre, 2 = in, 3 = post
    Frame(TreeNode node) { this.node = node; }
}

Algorithm.

  1. If the root is null, return three empty lists.
  2. Push a frame for the root with state 1.
  3. While the stack is not empty, look at the top frame and act according to its state as described above.
static List<List<Integer>> oneStack(TreeNode root) {
    List<Integer> pre = new ArrayList<>(), in = new ArrayList<>(), post = new ArrayList<>();
    if (root == null) return List.of(pre, in, post);
    Deque<Frame> stack = new ArrayDeque<>();
    stack.push(new Frame(root));
    while (!stack.isEmpty()) {
        Frame top = stack.peek();
        if (top.state == 1) {                 // first visit: preorder, then descend left
            pre.add(top.node.val);
            top.state = 2;
            if (top.node.left != null) stack.push(new Frame(top.node.left));
        } else if (top.state == 2) {          // second visit: inorder, then descend right
            in.add(top.node.val);
            top.state = 3;
            if (top.node.right != null) stack.push(new Frame(top.node.right));
        } else {                              // third visit: postorder, the node is finished
            post.add(top.node.val);
            stack.pop();
        }
    }
    return List.of(pre, in, post);
}

Dry run on the three-node tree [1, 2, 3] (2 is the left child, 3 the right child of 1). Frames are written as node:state, stack bottom to top.

Step Top Action Stack after pre in post
1 1:1 pre 1, push left child 2 [1:2, 2:1] 1    
2 2:1 pre 2, no left child [1:2, 2:2] 1 2    
3 2:2 in 2, no right child [1:2, 2:3] 1 2 2  
4 2:3 post 2, pop [1:2] 1 2 2 2
5 1:2 in 1, push right child 3 [1:3, 3:1] 1 2 2 1 2
6 3:1 pre 3 [1:3, 3:2] 1 2 3 2 1 2
7 3:2 in 3 [1:3, 3:3] 1 2 3 2 1 3 2
8 3:3 post 3, pop [1:3] 1 2 3 2 1 3 2 3
9 1:3 post 1, pop [] 1 2 3 2 1 3 2 3 1

The result is preorder [1, 2, 3], inorder [2, 1, 3], postorder [2, 3, 1].

Complexity. Time O(n): each node gets one frame, which is examined exactly three times. Space O(h): the stack holds one frame per node on the current root-to-node path. Because the stack lives on the heap, a chain of 10^5 nodes is no problem; the Java tests check exactly that.

Edge cases and pitfalls