Tree Traversals Explained — Inorder, Preorder & Postorder With Real Uses

Every time your IDE folds or unfolds a directory, every time a compiler evaluates an expression like 3 + (4 * 2), and every time a database engine builds a query plan — a tree traversal is running under the hood. These aren't academic exercises; they're the backbone of tools you use every day. Understanding traversals is what separates developers who can reason about recursive structures from those who just copy-paste solutions and hope for the best.

The problem traversals solve is deceptively simple: a tree has no 'natural' reading order the way an array does. Arrays are linear — element 0, then 1, then 2. Trees branch. You need a deliberate strategy for visiting every node exactly once without missing any or doubling back. The three classical strategies — preorder, inorder, and postorder — each prioritise a different relationship between a node and its children, and that priority determines what the output is useful for.

By the end of this article you'll know not just how to implement all three traversals recursively and iteratively in Java, but — more importantly — you'll know which one to reach for when solving a real problem. You'll be able to look at a coding challenge and immediately say 'this needs postorder because I have to process children before parents' rather than guessing. That intuition is what interviewers are actually testing.

Tree Traversal Algorithms — Plain English and Rules

A binary tree traversal visits every node exactly once. There are four main orders:

Inorder (Left, Root, Right): Visit the left subtree, then the current node, then the right subtree. For a Binary Search Tree, inorder traversal produces elements in sorted ascending order — this is its most important property.

Preorder (Root, Left, Right): Visit the current node first, then recurse into left, then right. Used to create a copy of the tree or serialize it to a flat list.

Postorder (Left, Right, Root): Visit both subtrees before the current node. Used to delete a tree (process children before parent) or evaluate expression trees.

Level-order (BFS): Visit nodes level by level from top to bottom, left to right. Uses a queue, not recursion. Used to find tree height, check if balanced, or serialize by level.

Memory trick: the prefix tells you when the Root is visited relative to children: Pre-order = Root first. In-order = Root in between (2nd). Post-order = Root last.

Worked Example — All Four Traversals on the Same Tree

Tree: 1 / \ 2 3 / \ 4 5

Inorder (L-Root-R): Go left from 1 -> 2 -> 4. 4 has no children. Visit 4. Back to 2. Visit 2. Go right: visit 5. Back to 1. Visit 1. Go right: visit 3. Result: [4, 2, 5, 1, 3]

Preorder (Root-L-R): Visit 1. Go left: visit 2. Go left: visit 4. Back to 2. Go right: visit 5. Back to 1. Go right: visit 3. Result: [1, 2, 4, 5, 3]

Postorder (L-R-Root): Go left from 1 to 2 to 4. Visit 4. Back to 2. Go right to 5. Visit 5. Visit 2. Back to 1. Go right: visit 3. Visit 1. Result: [4, 5, 2, 3, 1]

Level-order (BFS): Level 0: visit 1. Level 1: visit 2, 3. Level 2: visit 4, 5. Result: [1, 2, 3, 4, 5]

The Anatomy of a Traversal: Depth-First Search (DFS) Strategies

In a Depth-First Search, we explore as far as possible along each branch before backtracking. The difference between the three types is simply when you 'visit' (process) the current node relative to its subtrees.

• Preorder (Root, Left, Right): Visit the parent before the children. Perfect for cloning trees or prefix notation.
• Inorder (Left, Root, Right): Visit the left child, then the parent, then the right. On a Binary Search Tree (BST), this results in sorted order.
• Postorder (Left, Right, Root): Visit the children before the parent. Essential for deleting nodes or calculating directory sizes where you need the sum of children first.

package io.thecodeforge.dsa;

class Node {
    int data;
    Node left, right;
    public Node(int item) { data = item; }
}

public class TreeTraversal {
    // Inorder: Left -> Root -> Right
    public void printInorder(Node node) {
        if (node == null) return;
        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
    }

    // Preorder: Root -> Left -> Right
    public void printPreorder(Node node) {
        if (node == null) return;
        System.out.print(node.data + " ");
        printPreorder(node.left);
        printPreorder(node.right);
    }

    // Postorder: Left -> Right -> Root
    public void printPostorder(Node node) {
        if (node == null) return;
        printPostorder(node.left);
        printPostorder(node.right);
        System.out.print(node.data + " ");
    }
}

Frequently Asked Questions