DFS and BFS

These acronyms, of course, refer to depth first search and breadth first search. These are two different high-level algorithms for traversing a tree data structure.

In these examples, let’s consider a binary tree in which each node is an integer, and we want to search for a node in the tree with a certain integer value.

Depth First Search

Depth first search works by starting from the root node, then following a branch until it reaches a leaf node — a node with node children. Then it backtracks back to the root node and follows the next branch down from there.

Breadth First Search

Breath first search, conversely, checks nodes on the same depth — hence, breadth, not depth. It starts at the root node, then traverses all children one level down, then moves on to the next level and traverses all children two levels down, so on and so forth.

Implementation

This can vary greatly, but for a rough overview, we can consider:

• Implementing DFS with a stack — last in first out. Traversing all nodes of the tree as we discover them. Read a node, put it’s children in the stack and read them as we discover them. Can use a recursive implementation.
• Implementing BFS with a queue — first in, first out. Add items to the queue as we discover them, then traverse them later when we enter that depth.

Comparison

• Depth first search preserves shape, whereas breadth first search does not