Binary Tree Traversal Explained in Depth (Preorder, Inorder, Postorder with Java Code)

 Binary Tree Traversals (In Depth Guide)

Ye topic bahut important hai kyunki:

• Tree ko read kaise karna hai — traversal se pata chalta hai

• 70% tree interview questions traversal based hote hain

• Recursion ka real use yahi se start hota hai

• DFS aur BFS concepts yahi se clear hote hain

 What is Tree Traversal? 

Tree Traversal is the process of visiting every node in a tree data structure exactly once in a specific order. Since a tree is hierarchical and non-linear, we cannot simply iterate over it like arrays or linked lists. Instead, we follow systematic traversal techniques to access nodes. Traversal ensures that all nodes are processed, whether for searching, printing, evaluating expressions, or performing modifications. Traversal techniques are mainly divided into two categories: Depth First Search (DFS) and Breadth First Search (BFS). DFS explores branches deeply before moving to the next branch, while BFS explores level by level. Understanding traversal is essential for solving advanced tree-based problems.

---

Two Main Categories of Traversal

 Depth First Search (DFS)

Isme hum tree ko depth me explore karte hain.

DFS ke 3 types:

• Preorder

• Inorder

• Postorder

---

 Breadth First Search (BFS)

Isme hum level by level explore karte hain.

Isko Level Order Traversal bhi bolte hain.

---

Example Tree

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

---

 Depth First Traversals (DFS)

---

 Preorder Traversal

Rule:

Root → Left → Right

Definition

Preorder traversal is a depth-first traversal method where the root node is visited first, followed by recursively visiting the left subtree and then the right subtree. It is called preorder because the root node is processed before its children. This traversal is useful when we want to copy or serialize a tree structure since it preserves the parent-child relationship in a top-down manner.

Output:

1 2 4 5 3 6 7

Java Code

void preorder(TreeNode root) {
    if (root == null) return;

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

---

 Inorder Traversal

Rule:

Left → Root → Right

Definition 

Inorder traversal is a depth-first traversal technique where the left subtree is visited first, followed by the root node, and finally the right subtree. In Binary Search Trees (BST), inorder traversal produces elements in sorted order. This makes inorder traversal extremely important in search-based tree problems. It helps in validating whether a tree follows BST properties.

Output:

4 2 5 1 6 3 7

Java Code

void inorder(TreeNode root) {
    if (root == null) return;

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

---

Postorder Traversal

Rule:

Left → Right → Root

Definition 

Postorder traversal is a depth-first traversal method where the left subtree is visited first, followed by the right subtree, and finally the root node. The root is processed last. This traversal is useful in scenarios such as deleting a tree, because children are removed before their parent. It is also used in expression tree evaluation where operands are processed before operators.

Output:

4 5 2 6 7 3 1

Java Code

void postorder(TreeNode root) {
    if (root == null) return;

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

---

Breadth First Traversal (Level Order)

Rule:

Level by Level

Definition (120 Words)

Level Order Traversal is a breadth-first traversal method where nodes are visited level by level from left to right. Unlike DFS, which goes deep into a branch, BFS explores all nodes at the current depth before moving to the next level. This traversal uses a Queue data structure internally. Level order traversal is useful in shortest path problems, tree height calculation, and structural analysis of trees.

Output:

1 2 3 4 5 6 7

Java Code

import java.util.*;

void levelOrder(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.data + " ");

        if (node.left != null)
            queue.add(node.left);

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

---

Time Complexity (Important)

All traversals:

O(n)

Kyuki har node ek baar visit hota hai.

---

 DFS vs BFS Comparison

DFS	BFS
Uses recursion	Uses queue
Goes deep first	Goes level by level
Less memory (sometimes)	More memory (queue)

---

 Basic Question

Inorder traversal BST me sorted output kyun deta hai?

---

 Thinking Question

Agar ek binary tree me sirf right child ho har node ka, to inorder aur preorder output same hoga ya different?

---