liveBook · Manning

Traversal

As explained in Algorithms Every Programmer Should Know

Traversal is the process of visiting the elements of a data structure in sequence to locate or process them.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines linked-list scans from the head, notes their O(N) cost, and contrasts tree searches by depth and layer.
Examples
Traces scanning from a linked-list head and searching for node 8 from tree root 5 with DFS or BFS.
What you can do after
Apply traversal by scanning linked-list nodes from the head or searching tree nodes with BFS or DFS.
How it connects
Connects traversal to linked lists, doubly linked lists, trees, breadth-first search, depth-first search, stacks, and queues.

Also explained in

Compare how 5 books explain traversal →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.