☕ DSA Java Articles

Topics › Binary Trees › Traversals

Preorder, Inorder, and Postorder Traversal in one Traversal

Easy TUF ID 2789 A2Z

Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return its preorder (node, left, right), inorder (left, node, right) and postorder (left, right, node) sequences, produced by a single traversal of the tree. Return them as a list of three lists [pre, in, post]. For an empty tree all three lists are empty.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in an int.

Example 1

tree (level order) = [1, 2, 3, 4, 5, 6, 7]

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

pre  = [1, 2, 4, 5, 3, 6, 7]
in   = [4, 2, 5, 1, 6, 3, 7]
post = [4, 5, 2, 6, 7, 3, 1]

Example 2

tree (level order) = [1, null, 2, 3]       // 1 -> right 2 -> left 3

pre  = [1, 2, 3]
in   = [1, 3, 2]                           // 1 has no left subtree, so it comes first
post = [3, 2, 1]

The key observation: a depth-first walk passes every node three times. It arrives at the node from its parent, it comes back after finishing the left subtree, and it comes back again after finishing the right subtree. Preorder, inorder and postorder are not three different walks; they are the same walk, written down at the first, second and third visit respectively. Once you see that, collecting all three at once is natural.

Approach 1: Three separate traversals

Intuition. The obvious way is to write the three textbook recursive functions and run each of them. It gives the right answer and is a useful reference, but it walks the tree three times, which is exactly what the problem asks us to avoid.

Algorithm.

  1. Run a recursive preorder, inorder and postorder, each filling its own list.
  2. Return the three lists.
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);
}

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

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

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) per traversal, so about 3n node visits in total. Space O(h) for the recursion, where h is the height of the tree, plus the output.

Approach 2: One recursive walk

Intuition. Look at the three functions above: they are identical except for the line where the value is recorded. Merge them into one function and record the value in all three places: into pre before the left call, into in between the two calls, and into post after the right call. Each node is entered once, and the recursion itself tells us which of the three visits we are at.

Algorithm.

  1. If the node is null, return.
  2. Append to pre, recurse left, append to in, recurse right, append to post.
static List<List<Integer>> oneRecursiveWalk(TreeNode root) {
    List<Integer> pre = new ArrayList<>(), in = new ArrayList<>(), post = new ArrayList<>();
    walk(root, pre, in, post);
    return List.of(pre, in, post);
}

static void walk(TreeNode node, List<Integer> pre, List<Integer> in, List<Integer> post) {
    if (node == null) return;
    pre.add(node.val);
    walk(node.left, pre, in, post);
    in.add(node.val);
    walk(node.right, pre, in, post);
    post.add(node.val);
}

Complexity. Time O(n): one walk, three constant-time appends per node. Space O(h) for the call stack. On a skewed tree with 10^5 nodes the recursion can overflow the JVM stack, which is why the sheet asks for an iterative version.

Approach 3: One iterative walk with a state per node

Intuition. To remove the recursion we have to store, for each node on the stack, what a recursive call would remember implicitly: how far it has got. That is a small number:

So the stack holds (node, state) pairs. We pop the top, act according to its state, and if the node is not finished we increase the state and push it back before pushing the child, so the child is processed first and the parent is waiting underneath with the right state when the child is done. This is exactly how a compiler implements recursion: a stack of frames, each with a “resume here” marker.

Algorithm.

  1. If the root is null, return three empty lists. Otherwise push (root, 1).
  2. While the stack is not empty, pop top:
    • state 1: append to pre, set state 2, push it back, push (left, 1) if the left child exists.
    • state 2: append to in, set state 3, push it back, push (right, 1) if the right child exists.
    • state 3: append to post.
  3. Return [pre, in, post].
static List<List<Integer>> oneIterativeWalk(TreeNode root) {
    List<Integer> pre = new ArrayList<>(), in = new ArrayList<>(), post = new ArrayList<>();
    if (root == null) return List.of(pre, in, post);
    Deque<Pair> st = new ArrayDeque<>();
    st.push(new Pair(root, 1));
    while (!st.isEmpty()) {
        Pair top = st.pop();
        if (top.state == 1) {
            pre.add(top.node.val);
            top.state = 2;
            st.push(top);
            if (top.node.left != null) st.push(new Pair(top.node.left, 1));
        } else if (top.state == 2) {
            in.add(top.node.val);
            top.state = 3;
            st.push(top);
            if (top.node.right != null) st.push(new Pair(top.node.right, 1));
        } else {
            post.add(top.node.val);
        }
    }
    return List.of(pre, in, post);
}

Dry run on the tree 1 with children 2 and 3 (stack written bottom to top):

pop action stack after pre in post
(1,1) pre 1, push (1,2), (2,1) (1,2) (2,1) 1    
(2,1) pre 2, push (2,2); no left child (1,2) (2,2) 1 2    
(2,2) in 2, push (2,3); no right child (1,2) (2,3) 1 2 2  
(2,3) post 2 (1,2) 1 2 2 2
(1,2) in 1, push (1,3), (3,1) (1,3) (3,1) 1 2 2 1 2
(3,1) pre 3, push (3,2) (1,3) (3,2) 1 2 3 2 1 2
(3,2) in 3, push (3,3) (1,3) (3,3) 1 2 3 2 1 3 2
(3,3) post 3 (1,3) 1 2 3 2 1 3 2 3
(1,3) post 1 empty 1 2 3 2 1 3 2 3 1

Complexity. Time O(n): every node is popped exactly three times, once per state, and each pop does constant work. Space O(h): at any moment the stack holds one entry per node on the current root-to-node path (plus at most the one child just pushed), never two entries for the same node.

Why is it correct? By induction on subtree size: when (v, 1) is pushed, the loop will emit the full traversals of v’s subtree before anything below v on the stack is touched. The left child’s pair sits on top of (v, 2), so the whole left subtree is finished before v is seen again; the same holds for the right subtree and (v, 3). That is precisely the order of the recursive walk in Approach 2.

Edge cases and pitfalls