1. What is Tree Traversal?

Tree traversal means visiting every node in a tree exactly once in a specific order. Since a binary tree is non-linear and hierarchical, there are multiple ways to traverse it.

Traversals help to:

• Process nodes in a meaningful order
• Search, insert, and delete efficiently
• Convert trees to other data formats (e.g., arrays, expressions)

There are two primary traversal types:

• Depth-First Traversal (DFS): Traverse as deep as possible down one branch before backing up.
• Breadth-First Traversal (BFS): Visit nodes level by level.

2. Depth-First Traversals

A. Inorder Traversal (Left → Root → Right)

• Traverse left subtree
• Visit root
• Traverse right subtree

        1
      /   \
     2     3
    / \     
   4   5    

Inorder Output: 4 2 5 1 3

Java Code:

void inorder(TreeNode node) {
    if (node != null) {
        inorder(node.left);
        System.out.print(node.data + " ");
        inorder(node.right);
    }
}

B. Preorder Traversal (Root → Left → Right)

• Visit root
• Traverse left subtree
• Traverse right subtree

Preorder Output: 1 2 4 5 3

Java Code:

void preorder(TreeNode node) {
    if (node != null) {
        System.out.print(node.data + " ");
        preorder(node.left);
        preorder(node.right);
    }
}

C. Postorder Traversal (Left → Right → Root)

• Traverse left subtree
• Traverse right subtree
• Visit root

Postorder Output: 4 5 2 3 1

Java Code:

void postorder(TreeNode node) {
    if (node != null) {
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.data + " ");
    }
}

3. Breadth-First Traversal (Level Order)

Level-wise visiting of nodes (top-down, left to right)

Level Order Output: 1 2 3 4 5

Java Code using Queue:

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

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

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

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