The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Tree Traversals

Next ►
►

You already know how to build binary trees; now it's time to visit them methodically. In a list there's only one reasonable way to walk the elements (first to last); in a tree, by contrast, at every node you have to decide: do I process the node before going down, between its two children, or after coming back up? Each answer defines a traversal with a name of its own — preorder, inorder, and postorder — and to those we add the level-order traversal, which doesn't dive deep but sweeps the tree floor by floor with a queue. Choosing the right traversal is what separates "touching every node" from "solving the problem": in TaskFlow, exporting the hierarchy, computing accumulated hours, and painting the org chart level by level use three different traversals. This lesson also reunites old friends: recursion and the explicit stack from module 3, and the queue from module 4.

Contents

  1. The problem: in what order do I visit the nodes?
  2. Preorder, inorder, and postorder: the three depth-first traversals
  3. Detailed trace: the three traversals on the same tree
  4. Level-order traversal: the queue takes the stage
  5. Iterative versions with an explicit stack
  6. When to use each traversal (with TaskFlow as your guide)

The problem: in what order do I visit the nodes?

Traversing a tree means visiting each node exactly once. With the recursive definition of a binary tree (a node + left subtree + right subtree), traversing it requires doing three things: processing the Node, traversing the Left subtree, and traversing the Right subtree. The only thing that distinguishes the depth-first traversals is when the node gets processed (we'll always keep left before right):

Traversal Order Mnemonic
Preorder N, L, R The node before its children
Inorder L, N, R The node between its children
Postorder L, R, N The node after its children

All three are depth-first traversals (DFS): they sink down one branch to the bottom before touching the next. The fourth traversal, level-order (BFS, breadth-first), breaks the mold: it visits every node at depth 0, then every node at depth 1, and so on. A preview for module 7: DFS and BFS are actually general graph exploration strategies; here we meet them in their domesticated version, on trees, where they're simpler because there are no cycles.

Preorder, inorder, and postorder: the three depth-first traversals

The three functions are nearly identical — only one line moves. We'll use this tree throughout the lesson:

graph TD
    A((10)) --> B((6))
    A --> C((15))
    B --> D((3))
    B --> E((8))
    C --> F((12))
    C --> G((20))
class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = BinaryNode(10)
root.left = BinaryNode(6)
root.right = BinaryNode(15)
root.left.left = BinaryNode(3)
root.left.right = BinaryNode(8)
root.right.left = BinaryNode(12)
root.right.right = BinaryNode(20)

def preorder(node, result):
    if node is None:
        return
    result.append(node.value)        # N first...
    preorder(node.left, result)      # ...then L...
    preorder(node.right, result)     # ...then R

def inorder(node, result):
    if node is None:
        return
    inorder(node.left, result)       # L first...
    result.append(node.value)        # ...N in the middle...
    inorder(node.right, result)      # ...then R

def postorder(node, result):
    if node is None:
        return
    postorder(node.left, result)     # L...
    postorder(node.right, result)    # ...R...
    result.append(node.value)        # ...and N last

for f in (preorder, inorder, postorder):
    r = []
    f(root, r)
    print(f.__name__, r)
# preorder  [10, 6, 3, 8, 15, 12, 20]
# inorder   [3, 6, 8, 10, 12, 15, 20]
# postorder [3, 8, 6, 12, 20, 15, 10]

Three observations before the trace:

  • All three cost O(n) in time (each node is visited once) and O(height) in memory — the call stack from module 3 ends up stacking as many calls as the deepest branch is deep.
  • In preorder, the root comes out first; in postorder, last. This detail will be key in the reconstruction exercise of 06-08.
  • Look at the output of inorder: [3, 6, 8, 10, 12, 15, 20]. Sorted. That's no coincidence: this tree satisfies (spoiler) the property that will define the next lesson, and the inorder of such a tree always comes out in ascending order. Consider this the formal announcement: in 06-04 this goes from curiosity to theorem and tool.

Detailed trace: the three traversals on the same tree

Let's follow preorder step by step, with the call stack in view (indentation = call depth):

preorder(10): appends 10                      → [10]
  preorder(6): appends 6                      → [10, 6]
    preorder(3): appends 3                    → [10, 6, 3]
      preorder(None) x2: return
    preorder(8): appends 8                    → [10, 6, 3, 8]
      preorder(None) x2: return
  preorder(15): appends 15                    → [10, 6, 3, 8, 15]
    preorder(12): appends 12                  → [10, 6, 3, 8, 15, 12]
    preorder(20): appends 20                  → [10, 6, 3, 8, 15, 12, 20]

Each call appends its value the moment it enters and then delegates. Now inorder on the left subtree (the pattern repeats higher up):

inorder(10)
  inorder(6)
    inorder(3)
      inorder(None): return   ← 3 has no left child
      appends 3                                → [3]
      inorder(None): return
    appends 6                 ← only after exhausting its ENTIRE left subtree → [3, 6]
    inorder(8)
      appends 8                                → [3, 6, 8]
  appends 10                  ← 10 waits for its whole left branch to finish → [3, 6, 8, 10]
  inorder(15) ...                              → [3, 6, 8, 10, 12, 15, 20]

And postorder: each node waits for both of its subtrees to finish — that's why 6 comes out after 3 and 8, and the root 10 comes out last of all. A visual trick for self-checking without tracing:

graph TD
    A(("10 ③")) --> B(("6 ②"))
    A --> C(("15 ⑥"))
    B --> D(("3 ①"))
    B --> E(("8 ④"))
    C --> F(("12 ⑤"))
    C --> G(("20 ⑦"))

Walk the outline of the tree starting at the root and going left: in preorder, jot down each node the first time you touch it on its left side; in inorder, when you pass underneath it (the numbers in the diagram are the inorder sequence); in postorder, the last time you touch it, on its right side. With a pencil and 20 seconds you can verify any traversal.

Level-order traversal: the queue takes the stage

To visit level by level (10, then 6 and 15, then 3-8-12-20), recursion doesn't help: depth isn't the order we want. The right tool is one you built in module 4 — a FIFO queue. The algorithm: enqueue the root; while the queue isn't empty, dequeue a node, process it, and enqueue its children. The children, entering at the back, wait their turn until the current level finishes.

from collections import deque      # module 4's deque: O(1) at both ends

def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()             # the oldest one leaves (FIFO)
        result.append(node.value)
        if node.left:
            queue.append(node.left)        # children go to the back of the queue
        if node.right:
            queue.append(node.right)
    return result

print(level_order(root))   # [10, 6, 15, 3, 8, 12, 20]

Trace of the queue's state (left = next to leave):

Step Leaves Enters Queue after Result
1 10 6, 15 [6, 15] [10]
2 6 3, 8 [15, 3, 8] [10, 6]
3 15 12, 20 [3, 8, 12, 20] [10, 6, 15]
4-7 3, 8, 12, 20 — [] [10, 6, 15, 3, 8, 12, 20]

And here a pending circle closes: the binaries_up_to(n) exercise from module 4 ("1, 10, 11, 100, 101...") was doing exactly this — each binary string s enqueued its "children" s+'0' and s+'1'; you were doing a level-order traversal of the perfect binary tree of all binary strings, without having seen a tree yet. This traversal is a BFS in every sense; in module 7 we'll generalize it to graphs, where it will need the visited set we previewed in 05-04 (in a tree it's unnecessary: with no cycles and a single parent, it's impossible to enqueue the same node twice). Cost: O(n) in time; in memory, O(maximum width) — in a perfect tree, the last level has ≈ n/2 nodes, so it can be O(n).

Iterative versions with an explicit stack

In module 3 you learned (with the nested subtasks and their RecursionError) that any recursion can be converted to iteration by managing the stack yourself. With very deep trees — a degenerate tree of 10,000 nodes exceeds Python's recursion limit — this conversion goes from elegance to necessity. Iterative preorder:

def iterative_preorder(root):
    if root is None:
        return []
    result = []
    stack = [root]                     # a Python list as a stack (module 3)
    while stack:
        node = stack.pop()             # LIFO: the last one pushed leaves first
        result.append(node.value)
        if node.right:                 # right FIRST!...
            stack.append(node.right)
        if node.left:                  # ...so the left ends up on top
            stack.append(node.left)
    return result

print(iterative_preorder(root))   # [10, 6, 3, 8, 15, 12, 20] — same as the recursive one

The counterintuitive detail: you push the right child before the left one, because the stack reverses — last in, first out, and we want to process the left one first. Compare with level_order: the same skeleton, swapping the queue for a stack. That symmetry (queue → level-order/BFS; stack → depth-first/DFS) is one of the most beautiful ideas in the course, and it will reappear verbatim in module 7.

Iterative inorder is subtler: you can't just process a node when you pop it, because its turn comes after its entire left subtree. The technique: slide down to the leftmost bottom, stacking the path, and on the way back up, process and jump to the right subtree.

def iterative_inorder(root):
    result = []
    stack = []
    node = root
    while stack or node is not None:
        while node is not None:        # 1) go down the left, stacking the path
            stack.append(node)
            node = node.left
        node = stack.pop()             # 2) no more left: this node's turn
        result.append(node.value)
        node = node.right              # 3) and now its right subtree
    return result

print(iterative_inorder(root))   # [3, 6, 8, 10, 12, 15, 20]

The stack reproduces by hand what the call stack did on its own: remembering the ancestors still waiting to be processed. (Iterative postorder is even more convoluted — two stacks or visited-marking — and is rarely needed; knowing it exists is enough.)

When to use each traversal (with TaskFlow as your guide)

The general rule: ask yourself what needs to be done before processing a node.

You need... Traversal Why In TaskFlow
To process the parent before the children (create, copy, serialize) Preorder The parent must exist before hanging children Exporting the project tree with indentation
The values in ascending order (in a BST) Inorder Left < node < right (we'll prove it in 06-04) Task listing ordered by id
The children's results before processing the parent (aggregate, free, delete) Postorder The parent summarizes/depends on its subtrees Accumulated hours per project
To process by closeness to the root Level-order The queue guarantees depth order The "projects → categories → tasks" view, floor by floor

Another classic postorder example: deleting a tree in languages with manual memory management — you must free the children before the parent so you don't lose their references. And arithmetic expression trees give you all three: preorder = prefix notation, inorder = the usual notation with parentheses, postorder = the reverse Polish notation we evaluated with a stack in module 3.

Two of TaskFlow's uses, in code. The preorder that exports the hierarchy (it's the show function from 06-01! — it processed the node and then the children: it was a preorder without knowing it) and the postorder that accumulates hours:

def accumulated_hours(node):
    """Hours of the subtree: its own plus those of all descendants.
    Each node carries in value a dict with at least {'title', 'hours'}."""
    if node is None:
        return 0
    children_total = sum(accumulated_hours(c) for c in [node.left, node.right])
    return node.value["hours"] + children_total     # the parent, AFTER its children

There's no way to know what a project costs without first adding up its parts: the nature of the problem forces postorder. (In 06-08 we'll do it at scale, with budgets over the generic tree.)

Common Mistakes and Tips

  • Pushing the left child first in iterative preorder. The stack reverses the order: right first, left second. It's the number-one slip; if your iterative preorder comes out "mirrored", this is why.
  • Using a stack for the level-order traversal (or a queue for DFS). The auxiliary structure is the traversal: stack → depth-first, queue → level-order. Mix them up and you get the other traversal by accident.
  • Processing the node at the wrong moment. Computing accumulated totals in preorder forces contortions; in postorder they come out on their own. Before coding, decide which way information must flow: from parents to children (preorder, like the depth parameter) or from children to parents (postorder, like the hours).
  • Trusting recursion with trees of unknown depth. A degenerate tree with thousands of nodes blows the call stack (RecursionError, module 3). For data from external sources, the iterative version is the defensive one.
  • Tip: memorize this example tree's outputs (pre: root first; in: sorted; post: root last). Having one solved case in your head lets you validate any implementation in seconds.

Exercises

Exercise 1: level-order, with the levels separated

Modify level_order so it returns a list of lists, one per level: [[10], [6, 15], [3, 8, 12, 20]]. Hint: before draining each level, len(queue) tells you how many nodes it contains.

Exercise 2: maximum depth without recursion

Using the result of exercise 1 (or a queue directly), write iterative_height(root) that computes the tree's height without recursion. For the lesson's tree it must return 2.

Exercise 3: exporting TaskFlow in iterative preorder

On the generic tree (TreeNode from 06-01, with its children list), write an iterative export(root) with an explicit stack that returns the indented lines of the hierarchy (like show from 06-01, but without recursion and returning a list). Hint: push (node, depth) pairs, and push the children in reverse order to preserve their natural order.

Solutions

Solution 1

def levels_separated(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)            # everything in it NOW belongs to this level
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

print(levels_separated(root))   # [[10], [6, 15], [3, 8, 12, 20]]

Comment: the key is the snapshot level_size = len(queue) — at the start of each while iteration, the queue contains exactly one complete level, and the for consumes it while enqueuing the next. Without the snapshot, the freshly enqueued children would mix into the current level. This "process in batches" pattern is an interview classic.

Solution 2

def iterative_height(root):
    return len(levels_separated(root)) - 1

print(iterative_height(root))   # 2

Comment: the height is the number of levels minus 1 (the root is level 0), and as a bonus the empty tree returns −1, consistent with 06-02's convention. With no recursion there's no possible RecursionError: this version survives the degenerate tree that would take down the recursive one.

Solution 3

def export(root):
    if root is None:
        return []
    lines = []
    stack = [(root, 0)]                      # (node, depth) pairs
    while stack:
        node, depth = stack.pop()
        if isinstance(node.value, dict):
            label = f"[{node.value['id']}] {node.value['title']}"
        else:
            label = node.value
        lines.append("    " * depth + label)
        for child in reversed(node.children):    # reversed: the first ends up on top
            stack.append((child, depth + 1))
    return lines

Comment: two ideas combine. First: since there's no call stack to remember the depth, we carry it in the tuple — the manual equivalent of 06-01's depth parameter. Second: reversed(node.children) generalizes the "right before left" trick to n children. The result is identical line by line to show's, but immune to RecursionError: TaskFlow can now export hierarchies of any depth.

Conclusion

You now command the four canonical ways to visit a tree: preorder (node first — copy, serialize, export), inorder (node in the middle — with that sorted output whose secret is revealed in the next lesson), postorder (node last — aggregating and freeing from children to parents), and level-order (module 4's queue sweeping floor by floor — your first BFS, which will leap to graphs in module 7). And you know how to ground them with an explicit stack when depth threatens recursion. With the structure (06-02) and the traversals (06-03) in hand, it's time for the payoff: adding a placement rule to the binary tree — smaller to the left, larger to the right — and watching how, all at once, searching costs O(height), inorder hands you the data sorted, and the range queries the hash table couldn't answer ("priority between 1 and 3") finally have an owner. That's the binary search tree, and it's the next lesson.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved