Traversal visits elements in sequence to locate or process them. In a linked list, start at the head and follow each node’s pointer; unlike an array, you cannot jump directly to a position. This scan takes O(N). section 1.4.2
For tree searches, traversal can follow either of two patterns:
- Depth-first search (DFS) follows a path down to a leaf, then backtracks to explore another path. section 1.4.4
- Breadth-first search (BFS) visits a layer of nodes before moving to the next; a queue keeps track of where to explore. section 1.4.4
Searching a tree
Starting at root node 5 and looking for 8, DFS dives down a path and backtracks when needed; BFS checks each layer before descending. section 1.4.4
Figure 1.4 Illustration of a linked list with four nodes. Each node has data and a pointer pointing to the next node. The start of the linked list is marked as head. The end of the linked list is identified if the next pointer is null.
A four-node linked-list diagram shows how traversal follows next pointers from the head. section 1.4.2
Figure 1.9 The two fundamental strategies for searching non-linear data structures. Left: Depth-First Search (DFS) goes deep down a single path to a leaf node. Right: Breadt-First Search (BFS) expands outward, exploring all the neighboring nodes layer by layer before descending to the next level.
A side-by-side diagram contrasts deep-path DFS with layer-by-layer BFS. section 1.4.4




