TLDR: Trees are non-linear, meaning there isn't just one way to read them. "Traversal" is simply the specific order in which you visit every node. This guide breaks down the four essential strategies—Preorder, Inorder, Postorder, and Level Order—using simple analogies and clear code.

---

What is Tree Traversal? (The "No-Jargon" Explanation)

Imagine you are exploring a Maze (the Tree). You are at the entrance (Root). You need to visit every single room (Node) exactly once to find treasure.

How do you do it? You need a System.

• Random Walking: You might miss a room or visit one twice. (Bad).
• Systematic Traversal: You follow a strict rule, like "Always go Left first, then check the Room, then go Right." (Good).

In computer science, because trees branch out, we can't just say "Next, Next, Next" like in an Array. We have to choose a direction.

---

The Four Main Strategies

We group these into two categories: Depth First Search (DFS) and Breadth First Search (BFS).

1. Preorder Traversal (DFS)

• Rule: Root $\rightarrow$ Left $\rightarrow$ Right.
• Analogy: A CEO making an announcement. "I (Root) will speak first, then my VP of Sales (Left), then my VP of Engineering (Right)."
• Use Case: Copying a tree structure.

2. Inorder Traversal (DFS)

• Rule: Left $\rightarrow$ Root $\rightarrow$ Right.
• Analogy: A polite host. "I will let my guest on the left go first, then I (Root) will go, then my guest on the right."
• Use Case: Getting sorted data from a Binary Search Tree (BST).

3. Postorder Traversal (DFS)

• Rule: Left $\rightarrow$ Right $\rightarrow$ Root.
• Analogy: A demolition crew. "Destroy the building on the left, destroy the building on the right, and finally destroy the command center (Root) last."
• Use Case: Deleting a tree safely (children must be deleted before parent).

4. Level Order Traversal (BFS)

• Rule: Level by Level (Top to Bottom, Left to Right).
• Analogy: Reading a book. You read line 1, then line 2, then line 3.
• Use Case: Finding the shortest path in a network.

---

Deep Dive: How Traversal Actually Works

Let's trace these algorithms on a concrete Toy Tree.

Toy Dataset (The Tree)

       1 (Root)
      /      \
     2        3
    / \
   4   5

A. Preorder (Root -> Left -> Right)

The Algorithm's Path:

1. Start at 1. Print 1.
2. Go Left to 2. Print 2.
3. Go Left to 4. Print 4. (4 has no children, return).
4. Back at 2, go Right to 5. Print 5. (5 has no children, return).
5. Back at 1, go Right to 3. Print 3.

Result: 1, 2, 4, 5, 3

B. Inorder (Left -> Root -> Right)

The Algorithm's Path:

1. Start at 1. Go Left to 2.
2. At 2, Go Left to 4.
3. At 4 (Left is null). Print 4. (Right is null). Return.
4. Back at 2. Print 2.
5. Go Right to 5. Print 5. Return.
6. Back at 1. Print 1.
7. Go Right to 3. Print 3.

Result: 4, 2, 5, 1, 3

C. The Math (Recursion Stack)

DFS traversals use a Stack (either the system call stack or an explicit one).

• Space Complexity: $O(H)$ where $H$ is the height of the tree.
  • In a skewed tree (like a linked list), $H = N$.
  • In a balanced tree, $H = \log N$.
• Time Complexity: $O(N)$ because we visit every node exactly once.

---

Implementation: The Code

Here is the Java code for all three DFS traversals using Recursion.

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class TreeTraversal {

    // 1. Preorder: Root -> Left -> Right
    public void preorder(TreeNode node) {
        if (node == null) return;
        System.out.print(node.val + " "); // Process Root
        preorder(node.left);              // Recurse Left
        preorder(node.right);             // Recurse Right
    }

    // 2. Inorder: Left -> Root -> Right
    public void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);               // Recurse Left
        System.out.print(node.val + " "); // Process Root
        inorder(node.right);              // Recurse Right
    }

    // 3. Postorder: Left -> Right -> Root
    public void postorder(TreeNode node) {
        if (node == null) return;
        postorder(node.left);             // Recurse Left
        postorder(node.right);            // Recurse Right
        System.out.print(node.val + " "); // Process Root
    }
}

---

Real-World Application: Mathematical Expressions

Compilers use Expression Trees to understand math.

• Expression: (A + B) * C
• Tree Structure:

      *
     / \
    +   C
   / \
  A   B
  

Traversals reveal different notations:

1. Inorder (Left, Root, Right): A + B * C (Infix Notation - Human readable).
2. Postorder (Left, Right, Root): A B + C * (Reverse Polish Notation - Used by old calculators and stack machines).
3. Preorder (Root, Left, Right): * + A B C (Prefix Notation).

---

Summary & Key Takeaways

• Traversal is the order of visiting nodes.
• DFS (Depth First): Uses a Stack (Recursion). Goes deep first.
  • Preorder (Root first)
  • Inorder (Root middle)
  • Postorder (Root last)
• BFS (Breadth First): Uses a Queue. Goes level by level.

---

Practice Quiz: Test Your Knowledge

1. Scenario: You want to print the values of a Binary Search Tree (BST) in perfectly sorted order (ascending). Which traversal do you use?

   • A) Preorder
   • B) Inorder
   • C) Postorder

2. Scenario: You need to delete a tree from memory. You must delete the children before you delete the parent node to avoid memory leaks. Which traversal is safe?

   • A) Preorder
   • B) Inorder
   • C) Postorder

(Answers: 1-B, 2-C)

---

What's Next?

Now that you can walk through a tree, let's look at a special kind of tree that keeps itself sorted automatically. In the next post, we explore Binary Search Trees (BST) and how they make searching lightning fast.