BFS and DFS algorithms in Ruby

In this article I’ll consider two common approaches to implementing depth-first search and breadth-first search in Ruby.

Tree

Ruby has no built-in class for initializing Binary Tree data structure. Tree is just a restricted form of a Graph which have a parent-child relationship.

Here is the simplest definition for a binary tree node:

Let’s build a tree as an example:

This tree can be illustrated by the image below.

DFS (Depth-first search)

Output is next:

DFS algorithm starts with root node then explores each node in-depth, then goes to the next node and does the same until it goes around the whole tree.

BFS (Breadth-first search)

Result:

BFS algorithm also starts with root node, but unlike with the DFS algorithm, here we took each value on the same level of depth.

Maximum Depth of Binary Tree

Let’s consider small task solved through DFS.

Given an example B-tree:

Ruby Solution

Here we are calculating depth by incrementing the variable for each breadth iteration.

Software Engineer. Interested in Full-Stack Development and DevOps.