Tree Traversals — I Expected Graphs, Got Something Way Easier

March 10, 2026. Day 22.

I walked into tree traversals expecting another graphs situation.

The name alone — tree traversals — sounded complex. Technical. Intimidating. Graphs carried that same energy and delivered on the difficulty.

Tree traversals didn't.

Difficulty rating — 4.5 out of 10. One of the smoothest topics in this entire journey so far.

What Is Tree Traversal?

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

Four ways to do it:

• BFS — level by level, wide first

• DFS Pre-Order — root first, then left, then right

• DFS In-Order — left first, then root, then right

• DFS Post-Order — left first, then right, then root last

Two categories — BFS goes wide, DFS goes deep.

BFS — Breadth First Search

Goes level by level, left to right.

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

Level 1 → 50
Level 2 → 30, 70
Level 3 → 20, 40, 60, 80

Output: [50, 30, 70, 20, 40, 60, 80]

Uses a queue — FIFO from earlier in the journey. That connection made it click immediately.

def BFS(self):
    result = []
    queue = []

    if self.root:
        queue.append(self.root)

    while len(queue) > 0:
        current = queue.pop(0)           # remove from front (FIFO)
        result.append(current.value)

        if current.left:
            queue.append(current.left)   # add left child to back
        if current.right:
            queue.append(current.right)  # add right child to back

    return result

Why pop(0) and not pop()?

pop() removes from the back — that's a stack (LIFO), which gives you DFS.
pop(0) removes from the front — that's a queue (FIFO), which gives you BFS.

One character difference. Completely different traversal. That detail took a second to catch.

Step by step:

start:   queue = [50]

step 1:  pop 50  → add 30, 70   → queue = [30, 70]
step 2:  pop 30  → add 20, 40   → queue = [70, 20, 40]
step 3:  pop 70  → add 60, 80   → queue = [20, 40, 60, 80]
step 4:  pop 20  → no children  → queue = [40, 60, 80]
step 5:  pop 40  → no children  → queue = [60, 80]
step 6:  pop 60  → no children  → queue = [80]
step 7:  pop 80  → no children  → queue = []

output: [50, 30, 70, 20, 40, 60, 80] ✅

Real-world use: Google Maps finding the nearest location. Social networks surfacing mutual friends — people closest to you first, before people further away.

DFS — The Surprise of the Day

I expected DFS to be harder than BFS. Three variations — pre-order, in-order, post-order — sounded like three separate things to learn.

It wasn't.

All three use the exact same code structure. The only difference is where result.append() sits.

That was the biggest surprise of today.

DFS Pre-Order — Root First

current → left → right

def dfs_pre_order(self):
    result = []

    def traverse(current):
        result.append(current.value)    # append FIRST
        if current.left:
            traverse(current.left)
        if current.right:
            traverse(current.right)

    traverse(self.root)
    return result

Output: [50, 30, 20, 40, 70, 60, 80]

Root 50 comes first — then it goes deep left, then right.

Real-world use:

• Copying a tree — parent must exist before you can attach children to it.

• File systems — parent folder prints before its contents.

• HTML rendering — <div> opens before <h1> and <p> inside it.

DFS In-Order — The Sorted One

left → current → right

def dfs_in_order(self):
    result = []

    def traverse(current):
        if current.left:
            traverse(current.left)
        result.append(current.value)    # append MIDDLE
        if current.right:
            traverse(current.right)

    traverse(self.root)
    return result

Output: [20, 30, 40, 50, 60, 70, 80]  ← sorted ✅

Always sorted in a BST. Not magic — pure logic.

The BST rule says left is always smaller, right is always bigger. In-order follows that exact rule — left first, current in the middle, right last. Smallest to largest, naturally.

Real-world use:

• Database indexing — sorted output powers efficient search.

• Validating a BST — if the in-order output is sorted, the tree is valid.

• Expression trees — 3 + 4 * 2 evaluated in the correct mathematical order.

DFS Post-Order — Children Before Parent

left → right → current

def dfs_post_order(self):
    result = []

    def traverse(current):
        if current.left:
            traverse(current.left)
        if current.right:
            traverse(current.right)
        result.append(current.value)    # append LAST

    traverse(self.root)
    return result

Output: [20, 40, 30, 60, 80, 70, 50]

Root 50 comes last — children always finish before their parent.

Real-world use:

• Deleting a tree — children must be deleted before the parent. Delete the parent first and you lose reference to its children forever.

• Calculating folder size — you need the size of all subfolders before you can calculate the parent total.

• Math expressions — inner brackets resolve before outer ones.

(3 + 4) * 2
 └── calculate 3 + 4 first (children)
     then multiply the result (parent)

The Pattern That Made Everything Easy

Three DFS variations. Same structure. Only the append position changes.

def traverse(current):
    result.append()        # here = Pre-Order
    if current.left:
        traverse(current.left)
    result.append()        # here = In-Order
    if current.right:
        traverse(current.right)
    result.append()        # here = Post-Order

Once that pattern clicked, all three felt like one concept — not three separate ones.

If you understand BST, DFS comes naturally. The recursion, the left-right logic, the tree structure — it's all the same mental model you already built.

All Four Traversals Compared

BFS:          [50, 30, 70, 20, 40, 60, 80]  ← level by level
Pre-Order:    [50, 30, 20, 40, 70, 60, 80]  ← root first
In-Order:     [20, 30, 40, 50, 60, 70, 80]  ← sorted ✅
Post-Order:   [20, 40, 30, 60, 80, 70, 50]  ← root last

Root 50 tells the story:

• Pre-Order → index 0 — first

• In-Order → index 3 — middle

• Post-Order → index 6 — last

• BFS → index 0 — first (but a completely different path to get there)

Time and Space Complexity

All O(n) — every traversal visits every node exactly once.

What I Actually Learned Today

Tree traversals were easier than expected for one reason — the foundation was already there.

BST taught me left-right logic. Recursion taught me how functions call themselves. Stacks and queues taught me FIFO and LIFO. Tree traversals just combined everything I already knew.

That's the compound effect of learning DSA in order. Every hard topic becomes the foundation for the next one.

I didn't expect all three DFS variations to share the same code structure — that was the real surprise. One pattern, three outcomes, just by moving one line.

Good day.

Current Stats

• Date: March 10, 2026

• Day in journey: 22

• Topics completed: Linked Lists, Stacks, Queues, BST, Hash Tables, Graphs, Heap, Recursion, rBST, Tree Traversals

• Difficulty rating: 4.5/10

• Daily study time: 4 hours (6 AM – 10 AM)

• Next topic: Basic Sorting Algorithms

If you know BST, tree traversals will come naturally. That's all I can tell you.

Learning DSA too? What topic finally made everything click for you? Drop a comment.

— Avinash Negi

Resources:

• Scott Barrett's Python DSA Course