Iteration & Traversal

Overview

Iteration is the control-flow mechanism of repeating a code block until a condition is met, agnostic to any data structure. Traversal is the strategic application of iteration (or recursion) to visit every node or element in a specific data structure exactly once, guided by that structure's topology. Every traversal uses iteration as its engine, but not every iteration is a traversal.

Modern applications must process vast datasets stored in non-contiguous, dynamically allocated memory structures — linked lists, trees, graphs — where hardcoded indices fail at runtime. Traversal algorithms provide a principled, structure-aware navigation strategy that ensures complete, non-redundant coverage.

Where used: Linear traversal: reversing a linked list by maintaining prev/curr/next pointers in O(n) time and O(1) space, BFS traversal: finding the shortest path in an unweighted graph using a Queue for level-order discovery, DFS traversal: syntax tree evaluation in compilers and maze-solving via recursive stack-based backtracking

Why learn this

• Iteration and traversal are the absolute baseline for nearly all DSA problems — inability to write them fluently is an immediate disqualifier in top-tier interviews.
• Understanding the topological constraints of each data structure (linear vs. hierarchical vs. graph) dictates which traversal strategy is correct and why.
• Recognizing when NOT to traverse — using O(1) formulas (Gauss summation) or O(1) hash map lookups instead — is a hallmark of senior engineering thinking.

Aha moment

# Reverse a linked list: pure iteration or traversal?
class Node:
    def __init__(self, val): self.val, self.next = val, None

def reverse(head):
    prev, curr = None, head
    while curr:             # iteration engine
        nxt = curr.next     # traversal: following structural links
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Prediction: The while loop is just iteration — it could be replaced with a counter.

Common guess: This is just iteration because it uses a while loop.

The while loop IS the iteration engine, but what makes this a traversal is the explicit navigation of non-contiguous memory via structural links (curr.next). You cannot replace 'curr = nxt' with a counter — the next node's address is unknown until you follow the pointer. The topology of the linked list, not a numeric condition, governs the traversal.

Common mistakes

• Conflating iteration with traversal: A while loop that repeatedly halves a number until zero is iteration — it navigates no structure. Traversal carries the explicit intent of visiting every element of a specific collection. Misusing the terms reveals a shallow understanding of structural navigation.
• Modifying a collection during active traversal: Adding or deleting elements from a dynamic array or list while iterating over it causes index shifting, skipped elements, or iterator invalidation exceptions. Pointer state must be carefully managed if in-place mutation is required.
• Using DFS when BFS is required for shortest paths: DFS explores depth-first and does not guarantee shortest-path discovery in unweighted graphs. BFS's level-order Queue invariant mathematically ensures that the first time a node is reached, it is via the shortest path.

Glossary

dynamically allocated memory

Memory space that is requested and assigned while the program is running, not fixed beforehand.

topological constraints

The specific physical or logical structure that dictates how data is connected (like a line vs a tree).

iterator invalidation exceptions

An error that occurs when you try to change a collection while you are in the middle of looping through it.

Recall questions

• What is the precise distinction between iteration and traversal?
• Why is a Queue mathematically non-negotiable for BFS, and what invariant does it maintain?
• What are the space complexities of DFS and BFS on a binary tree, and what do their bounding variables represent?

Understanding checks

If you replace the Queue in a BFS implementation with a Stack, what traversal pattern does the algorithm produce, and why does this break shortest-path guarantees?

Replacing the Queue with a Stack produces DFS — the algorithm dives as deep as possible along one branch before backtracking. This breaks shortest-path guarantees because nodes are no longer discovered in level order; a deeper node on a longer path may be reached before a shallower node on a shorter path.

The Queue's FIFO property is the structural mechanism that enforces level-order discovery. The data structure choice is not cosmetic — it defines the fundamental traversal topology.

A developer writes: 'I used a for-loop to sum integers from 1 to n by iterating through a list. I traversed the list to get the answer.' Identify the two errors in this statement.

Error 1: It is iteration, not traversal — the loop processes numbers computationally, not nodes in a structural topology. Error 2: Even framing it as iteration reveals a missed optimization — Gauss's summation formula gives the answer in O(1) without any loop at all.

Traversal requires structural intent and a data structure to navigate. Recognizing when a mathematical shortcut eliminates the need for iteration entirely is a key signal of algorithmic maturity.

Practice tasks

Convert iterative BFS to DFS by changing one data structure

The starter code performs BFS level-order traversal on a binary tree (LeetCode 102). Modify it to perform DFS pre-order traversal by replacing exactly one data structure and adjusting the child insertion order. Add a comment explaining the invariant that each data structure maintains.

Continue learning

Previous: What is an Algorithm?

Previous: Tracing State & Loop Invariants

Return to DSA Roadmap