Binary Tree Traversals: Preorder, Inorder & Postorder Explained

When working with a binary tree, the real question isn't just how to move through its nodes — it's in what order you choose to visit them.

There are three fundamental depth-first search (DFS) traversals:

• Preorder

• Inorder

• Postorder

All three share the exact same recursive skeleton. The only thing that changes between them is when the current node gets processed relative to its subtrees.

Table of Contents

• The Basic Rule

• Preorder Traversal

• The Recursion Intuition

• Inorder Traversal

• Postorder Traversal

• Side-by-Side Comparison

• Time & Space Complexity

• How to Remember Them

The Basic Rule

Before comparing the three traversals, internalize one rule that never changes:

We always move left to right — left subtree before right subtree.

The only variable is where the current node is processed relative to that left-to-right movement:

Preorder   →  Root → Left → Right
Inorder    →  Left → Root → Right
Postorder  →  Left → Right → Root

Once you see where the root falls in each pattern, all three become trivial to derive on the spot — no memorization required.

We'll use this tree as a running example throughout:

        1
       / \
      2   3
     / \
    4   5

Preorder Traversal

Order: Root → Left → Right

At each node:

1. Visit the current node.

2. Traverse the left subtree.

3. Traverse the right subtree.

Walkthrough:

1. Start at 1 — it's the root, so process it first.

2. Descend into the left subtree rooted at 2. Process 2, then its left child 4 (no children → return), then its right child 5.

3. With the entire left subtree of 1 finished, move to the right subtree, 3.

Result:

1 → 2 → 4 → 5 → 3

The Recursion Intuition

This is the part that makes traversals click.

Every time recursion descends into a child, that child becomes the root of a smaller subtree — and the exact same rule (Root → Left → Right) applies again, just at a smaller scale.

        1
       /
      2
     /
    4

When recursion reaches 2, it doesn't need new logic — it just re-applies Root → Left → Right:

2 → 4 → ...

And at 4, both children are null, so the call returns immediately and control unwinds back up the call stack. This self-similar structure is exactly why recursion maps so naturally onto trees.

Preorder — C++

class Solution {
public:
    void preOrder(TreeNode* root, vector<int>& ans) {
        if (root == nullptr)
            return;

        ans.push_back(root->val);   // process root first

        preOrder(root->left, ans);
        preOrder(root->right, ans);
    }
};

vector<int>& ans is passed by reference, so every recursive call accumulates into the same result vector rather than building separate copies.

Preorder — Java

class Solution {
    public void preOrder(TreeNode root, List<Integer> ans) {
        if (root == null)
            return;

        ans.add(root.val);   // process root first

        preOrder(root.left, ans);
        preOrder(root.right, ans);
    }
}

The shape of the logic is identical:

Process Root → Traverse Left → Traverse Right

Inorder Traversal

Order: Left → Root → Right

Only one thing changes from preorder — when the root is processed:

1. Traverse the left subtree.

2. Visit the current node.

3. Traverse the right subtree.

Using the same tree, the result is:

4 → 2 → 5 → 1 → 3

Compare the two so far:

Preorder:  1 → 2 → 4 → 5 → 3
Inorder:   4 → 2 → 5 → 1 → 3

The tree hasn't changed. The recursive calls haven't changed. Only the position of the root's processing line moved.

Inorder — C++

class Solution {
public:
    void inOrder(TreeNode* root, vector<int>& ans) {
        if (root == nullptr)
            return;

        inOrder(root->left, ans);

        ans.push_back(root->val);   // process root in the middle

        inOrder(root->right, ans);
    }
};

Compared to preorder, ans.push_back(root->val) simply moved between the two recursive calls.

Inorder — Java

class Solution {
    public void inOrder(TreeNode root, List<Integer> ans) {
        if (root == null)
            return;

        inOrder(root.left, ans);

        ans.add(root.val);   // process root in the middle

        inOrder(root.right, ans);
    }
}

Traverse Left → Process Root → Traverse Right

Postorder Traversal

Order: Left → Right → Root

The root is processed only after both subtrees are fully traversed:

1. Traverse the left subtree.

2. Traverse the right subtree.

3. Visit the current node.

Using the same tree, the result is:

4 → 5 → 2 → 3 → 1

Again — same tree, same recursive calls, only the root's processing line moved, this time to the very end.

Postorder — C++

class Solution {
public:
    void postOrder(TreeNode* root, vector<int>& ans) {
        if (root == nullptr)
            return;

        postOrder(root->left, ans);
        postOrder(root->right, ans);

        ans.push_back(root->val);   // process root last
    }
};

Postorder — Java

class Solution {
    public void postOrder(TreeNode root, List<Integer> ans) {
        if (root == null)
            return;

        postOrder(root.left, ans);
        postOrder(root.right, ans);

        ans.add(root.val);   // process root last
    }
}

Traverse Left → Traverse Right → Process Root

Side-by-Side Comparison

Time & Space Complexity

All three traversals share the same complexity profile, since each visits every node exactly once:

• Time complexity: O(n), where n is the number of nodes.

• Space complexity: O(h) for the recursion call stack, where h is the height of the tree.

  • Balanced tree → O(log n).

  • Skewed (degenerate) tree → O(n), since the call stack depth equals the number of nodes.

Note that the output list itself also takes O(n) space, independent of the traversal order.

How to Remember Them

You don't need to memorize three separate algorithms — just the meaning of the prefixes:

• PREorder — pre = before → the root comes first: Root → Left → Right

• INorder — in = in between → the root comes in the middle: Left → Root → Right

• POSTorder — post = after → the root comes last: Left → Right → Root

Combine that with the one constant rule — left always comes before right — and the entire family of traversals collapses into a single idea:

PRE   → ROOT first
IN    → ROOT in the middle
POST  → ROOT last