Algo.Theory.Trees.TraverseOrders

1️⃣ What is a tree (in computer science)?

Think of a tree like a family tree 🌳

• One root (top person)
• Each node can have children
• No cycles (you can’t come back up in a loop)

Key words (very important)

• Node – one element
• Root – the top node
• Parent / Child
• Leaf – a node with no children
• Subtree – a node + all its descendants

---

2️⃣ What is a binary tree?

A binary tree is a special tree where:

👉 Each node has at most TWO children

• left child
• right child

That’s it. Nothing more.

Example (conceptually):

        A
       / \
      B   C
     /
    D

Rules:

• A node can have:
  • 0 children (leaf)
  • 1 child
  • 2 children
• But never more than 2

---

3️⃣ Other common types of trees (big picture)

Let’s zoom out a bit.

🌲 General Tree

• A node can have any number of children
• Example: file system, organization chart

---

🌲 Binary Tree (what we focus on)

• Max 2 children

---

🌲 Binary Search Tree (BST)

A binary tree + ordering rule:

• Left subtree → values less than node
• Right subtree → values greater than node

Used for searching fast.

---

🌲 Balanced Trees (AVL, Red-Black)

• Special BSTs
• Keep height small → fast operations

---

🌲 Heap

• Binary tree with heap property
• Used in priority queues

---

🌲 N-ary Tree

• Each node can have N children
• Example: game trees, XML/HTML DOM

4️⃣ What is tree traversal?

Traversal =
👉 “In what order do I visit nodes?”

Imagine:

• You’re walking through a tree
• You must decide when to visit the node relative to its children

5️⃣ Depth-First Traversals (DFS)

There are three classic DFS orders.

They all follow the same pattern:

Root – Left – Right
but the position of Root changes

🟥 Preorder Traversal

Order:

Root → Left → Right

Meaning:

“Visit the node before its children”

Example tree:

        A
       / \
      B   C
     /
    D

A, B, D, C

Mnemonic:

Pre = before children

class TreeNode {
    char val;
    TreeNode left;
static void preorder(TreeNode node) {
    if (node == null) return;

    System.out.print(node.val + " "); // Root
    preorder(node.left);              // Left
    preorder(node.right);             // Right
}

🟦 Inorder Traversal (special!)

Order:

Left → Root → Right

Same tree:

        A
       / \
      B   C
     /
    D

Inorder:

D, B, A, C

⚠️ Important:

• Only meaningful for binary trees
• In BST → inorder gives sorted order

static void inorder(TreeNode node) {
    if (node == null) return;

    inorder(node.left);               // Left
    System.out.print(node.val + " "); // Root
    inorder(node.right);              // Right
}

🟩 Postorder Traversal

Order:

Left → Right → Root

Same tree:

Postorder:

D, B, C, A

Mnemonic:

Post = after children

static void postorder(TreeNode node) {
    if (node == null) return;

    postorder(node.left);             // Left
    postorder(node.right);            // Right
    System.out.print(node.val + " "); // Root
}

6️⃣ Breadth-First Traversal (Level Order)

This is NOT DFS.

Order:

• Level by level
• Top to bottom
• Left to right

For the same tree:

A, B, C, D

Uses a queue, not recursion.

7️⃣ Why do traversal orders matter?

Because:

Traversals are like different camera angles of the same tree 📸

• Preorder tells you:
  • “Who
  • was created first”
• Postorder tells you:
  • “Who finishes last”
• Inorder tells you:
  • “Who is in the middle” (and sorted for BSTs)