Tree Traversal — Data Structure & Algrorithm

Imagine you have this tree:

If you want to process every node, you need a systematic way to visit them.

This process is called tree traversal.

Tree traversal is the process of visiting every node in a tree exactly once in a specific order.

There are four major tree traversal techniques you should know:

Preorder
Inorder
Postorder
Level Order

The first three are Depth-First Search (DFS) traversals, while level order is a Breadth-First Search (BFS) traversal.

Why Do We Need Tree Traversal?

Unlike an array:

10 → 20 → 30 → 40

a tree branches in different directions:

There isn't one obvious left-to-right order.

We need to decide when and in what order each node should be visited.

Different traversal methods produce different results from the same tree.

For example:

can produce:

Preorder  → 10 20 40 50 30
Inorder   → 40 20 50 10 30
Postorder → 40 50 20 30 10
Level Order → 10 20 30 40 50

The tree hasn't changed. Only the visiting order has changed.

Depth-First Traversal

In Depth-First Search, we go as deep as possible into one branch before coming back and exploring another branch.

The three main DFS traversals are:

Preorder
Inorder
Postorder

All three follow the same basic recursive structure:

Process current node
Explore left subtree
Explore right subtree

The difference is when we process the current node.

Preorder Traversal

Preorder follows:

Root → Left → Right

A simple way to remember it is:

Root comes first.

Consider:

Start at 10.

Process the root:

Then go left to 20:

10 → 20

Then go left to 40:

10 → 20 → 40

40 has no children, so go back to 20 and visit 50.

10 → 20 → 40 → 50

Finally, visit 30:

10 → 20 → 40 → 50 → 30

So:

Preorder:
10 20 40 50 30

Java Implementation

static void preorder(Node root) {

    if (root == null) {
        return;
    }

    System.out.print(root.data + " ");

    preorder(root.left);
    preorder(root.right);
}

Notice the order:

print(root.data);

preorder(root.left);
preorder(root.right);

The root is processed before its children.

Inorder Traversal

Inorder follows:

Left → Root → Right

Here, the root is processed between the left and right subtrees.

Using:

we first go to the left subtree.

From 10, go to 20.

From 20, go to 40.

40 has no left child, so process 40.

Then return to 20 and process it.

Then process 50.

Finally, return to 10 and process it.

Then process 30.

The result is:

40 → 20 → 50 → 10 → 30

So:

Inorder:
40 20 50 10 30

Java Implementation

static void inorder(Node root) {

    if (root == null) {
        return;
    }

    inorder(root.left);

    System.out.print(root.data + " ");

    inorder(root.right);
}

Notice:

inorder(left);

print(root);

inorder(right);

The root is processed between the two subtrees.

Important BST Property

Inorder traversal is especially important for a Binary Search Tree.

For example:

        50
       /  \
      30   70
     / \   / \
    20 40 60 80

Inorder traversal gives:

20 30 40 50 60 70 80

The values are sorted.

So remember:

Inorder traversal of a Binary Search Tree produces the values in sorted order.

Postorder Traversal

Postorder follows:

Left → Right → Root

Here, the root is processed after both children.

Using:

we first visit the left subtree.

Then:

Then process their parent:

After that, process the right subtree:

Finally, process the root:

So the result is:

40 → 50 → 20 → 30 → 10

Java Implementation

static void postorder(Node root) {

    if (root == null) {
        return;
    }

    postorder(root.left);
    postorder(root.right);

    System.out.print(root.data + " ");
}

Notice:

postorder(left);

postorder(right);

print(root);

The root is processed after both subtrees.

Level Order Traversal

The previous three traversals go deep into the tree.

Level order traversal works differently.

It visits nodes level by level, from top to bottom.

Consider:

The levels are:

Level 0 → 10
Level 1 → 20, 30
Level 2 → 40, 50

So the traversal is:

10 → 20 → 30 → 40 → 50

This is also called Breadth-First Search (BFS).

Why Does Level Order Use a Queue?

A queue follows:

FIFO
First In, First Out

That's perfect for processing tree levels.

Start by adding the root:

Queue:
10

Remove 10 and process it.

Then add its children:

Queue:
20, 30

Remove 20.

Add its children:

Queue:
30, 40, 50

Then process 30, followed by 40 and 50.

This gives:

10 → 20 → 30 → 40 → 50

Java Implementation

import java.util.LinkedList;
import java.util.Queue;

static void levelOrder(Node root) {

    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();

    queue.add(root);

    while (!queue.isEmpty()) {

        Node current = queue.remove();

        System.out.print(current.data + " ");

        if (current.left != null) {
            queue.add(current.left);
        }

        if (current.right != null) {
            queue.add(current.right);
        }
    }
}

The important idea is:

Add root
   ↓
Remove front node
   ↓
Process it
   ↓
Add its children
   ↓
Repeat

All Traversals Together

Let's use the same tree:

The four major traversals are:

Traversal	Order	Result
Preorder	Root → Left → Right	`10 20 40 50 30`
Inorder	Left → Root → Right	`40 20 50 10 30`
Postorder	Left → Right → Root	`40 50 20 30 10`
Level Order	Level by Level	`10 20 30 40 50`

The easiest way to remember the first three is:

Preorder:
Root Left Right

Inorder:
Left Root Right

Postorder:
Left Right Root

The position of Root changes.

Pre → Root first
In  → Root middle
Post → Root last

Recursive Tree Traversal

Tree traversal is naturally suited to recursion because every subtree is itself a tree.

For example:

        10
       /  \
      20   30

can be viewed as:

Tree
├── Root: 10
├── Left Subtree: 20
└── Right Subtree: 30

And the left subtree can itself contain more subtrees.

That's why the recursive structure is so simple:

if (root == null) {
    return;
}

Then:

traverse(root.left);
traverse(root.right);

The only thing that changes between preorder, inorder, and postorder is where we process the root.

Iterative Tree Traversal

We don't always have to use recursion.

We can also implement tree traversals using data structures such as a stack.

For example, preorder traversal can be implemented using a stack.

import java.util.Stack;

static void preorder(Node root) {

    if (root == null) {
        return;
    }

    Stack<Node> stack = new Stack<>();

    stack.push(root);

    while (!stack.isEmpty()) {

        Node current = stack.pop();

        System.out.print(current.data + " ");

        if (current.right != null) {
            stack.push(current.right);
        }

        if (current.left != null) {
            stack.push(current.left);
        }
    }
}

Why do we add the right child first?

Because the stack is LIFO.

If we push:

Right
Left

then Left comes out first.

So we get:

Root → Left → Right

This is a good example of how stacks are used in tree algorithms.

DFS vs BFS

The traversal methods can be divided into two groups.

DFS

Depth-First Search includes:

Preorder
Inorder
Postorder

DFS goes deep into a branch before exploring another branch.

It commonly uses:

Recursion
or
Stack

BFS

Breadth-First Search includes:

Level Order

BFS explores one complete level before moving to the next.

It commonly uses:

Queue

So:

DFS → Stack / Recursion
BFS → Queue

This is an important DSA relationship to remember.

Traversal of a Larger Tree

Consider:

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

Preorder

1 2 4 8 9 5 3 6 7

Because:

Root → Left → Right

Inorder

8 4 9 2 5 1 6 3 7

Because:

Left → Root → Right

Postorder

8 9 4 5 2 6 7 3 1

Because:

Left → Right → Root

Level Order

1 2 3 4 5 6 7 8 9

Because we process:

Level 0
1

Level 1
2 3

Level 2
4 5 6 7

Level 3
8 9

Applications of Tree Traversal

Tree traversal isn't just about printing nodes. It is the foundation of many important algorithms.

Searching

We can traverse a tree to find a particular value.

Finding Maximum or Minimum

We can visit every node and keep track of the largest or smallest value.

Calculating Height

We can recursively calculate the height of a tree.

Counting Nodes

Traversal can be used to count how many nodes exist.

Expression Trees

Postorder traversal can be useful when evaluating expression trees.

File Systems

Traversal can be used to visit files and directories.

Binary Search Trees

Inorder traversal can produce sorted data.

Graph Algorithms

The same DFS and BFS ideas are used heavily when we move from trees to graphs.

Time and Space Complexity

If a tree contains n nodes, every standard traversal visits each node once.

Therefore:

Time Complexity = O(n)

This applies to:

Preorder  → O(n)
Inorder   → O(n)
Postorder → O(n)
Level Order → O(n)

The space complexity depends on the tree's shape and the implementation.

For recursive DFS:

Space → O(h)

where h is the height of the tree.

For a balanced tree:

h ≈ log n

So the recursion stack is approximately:

O(log n)

For a completely skewed tree:

h = n

so the space can become:

O(n)

For level order traversal, the queue can hold an entire level. In the worst case, this can also require:

O(n)

space.

A Complete Java Example

Let's put all four traversals together:

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
    }
}

class Main {

    static void preorder(Node root) {

        if (root == null) {
            return;
        }

        System.out.print(root.data + " ");

        preorder(root.left);
        preorder(root.right);
    }

    static void inorder(Node root) {

        if (root == null) {
            return;
        }

        inorder(root.left);

        System.out.print(root.data + " ");

        inorder(root.right);
    }

    static void postorder(Node root) {

        if (root == null) {
            return;
        }

        postorder(root.left);
        postorder(root.right);

        System.out.print(root.data + " ");
    }

    static void levelOrder(Node root) {

        if (root == null) {
            return;
        }

        Queue<Node> queue = new LinkedList<>();

        queue.add(root);

        while (!queue.isEmpty()) {

            Node current = queue.remove();

            System.out.print(current.data + " ");

            if (current.left != null) {
                queue.add(current.left);
            }

            if (current.right != null) {
                queue.add(current.right);
            }
        }
    }

    public static void main(String[] args) {

        Node root = new Node(10);

        root.left = new Node(20);
        root.right = new Node(30);

        root.left.left = new Node(40);
        root.left.right = new Node(50);

        System.out.print("Preorder: ");
        preorder(root);

        System.out.print("\nInorder: ");
        inorder(root);

        System.out.print("\nPostorder: ");
        postorder(root);

        System.out.print("\nLevel Order: ");
        levelOrder(root);
    }
}

Output:

Preorder: 10 20 40 50 30
Inorder: 40 20 50 10 30
Postorder: 40 50 20 30 10
Level Order: 10 20 30 40 50

The Main Idea

Tree traversal means visiting every node of a tree in a specific order.

The four traversals you should remember are:

Preorder  → Root → Left → Right
Inorder   → Left → Root → Right
Postorder → Left → Right → Root
Level Order → Level by Level

The easiest way to remember them is to focus on where the Root appears:

Preorder:
ROOT comes first

Inorder:
ROOT comes between left and right

Postorder:
ROOT comes last

And remember the data structures behind them:

DFS → Recursion / Stack

BFS → Queue

Tree traversal is one of the most fundamental tree concepts in DSA because almost every tree problem involves visiting nodes in some particular order.