Traversing Trees: Eager vs Lazy Approaches

Tree structures are everywhere — from file systems and HTML DOMs to nested comment threads and syntax trees. Traversing them efficiently and clearly is a common but often overlooked challenge.

In this article, we'll compare eager and lazy approaches to tree traversal in Python. Specifically, we'll explore:

• What generator-based traversal looks like
• How it compares to traditional list-returning recursion
• Why the lazy approach might be more powerful than it first appears

---

🧰 Tree Structure Setup

Let's use a basic tree class with value and children:

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

Now let's create a simple tree:

root = Node("A", [
    Node("B", [Node("D"), Node("E")]),
    Node("C")
])

Visualized:

    A
   / \
  B   C
 / \
D   E

---

✅ Version 1: Eager Traversal (Return a List)

def traverse_to_list(node):
    result = [node.value]
    for child in node.children:
        result.extend(traverse_to_list(child))
    return result

Usage:

for val in traverse_to_list(root):
    print(val)

Output:

A
B
D
E
C

This version accumulates the full result list up front before returning anything.

---

✨ Version 2: Lazy Traversal (Using a Generator)

def traverse(node):
    yield node.value
    for child in node.children:
        yield from traverse(child)

Usage:

for val in traverse(root):
    print(val)

Output is identical:

A
B
D
E
C

But behavior is different:

• Values are yielded one-by-one
• No list is created
• Memory usage is minimal

---

📊 When to Use Each

Situation	Eager List	Lazy Generator
Small trees	✅ Simple and fast	✅ Also fine
Large trees	❌ Memory-heavy	✅ Better performance
Want full result	✅ Easy to get	❌ Must convert to list
Filter/map mid-traversal	❌ Requires extra steps	✅ Natural with generator expressions
Streaming use case	❌ Not viable	✅ Ideal

---

🧪 Bonus: Filtering While Traversing

Because generators yield values lazily, you can filter on the fly:

for val in traverse(root):
    if val.startswith("D"):
        print("Found:", val)

Or use a generator expression:

found = (v for v in traverse(root) if v.startswith("D"))
print(next(found))  # Found: D

---

🔍 What's Next?

In real-world scenarios, you usually start with nested dictionaries, flat lists, or JSON — not pre-built Node trees. Check out this article for more on building trees from raw data

---

🔄 TL;DR

• Generator-based tree traversal is clean, elegant, and memory-efficient.
• Recursive list-returning traversal is simple but can become inefficient.
• Use generators when you want laziness, streaming, or in-place filtering.

Both techniques have their place — the key is knowing which one matches your use case.