BFS and DFS algorithms in Ruby

Kirill Shevchenko
2 min readJul 31, 2021

--

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:

class Node
attr_accessor :val, :left, :right
def initialize(val)
@val = val
@left, @right = nil, nil
end
end

Let’s build a tree as an example:

root = Node.new(3)child_l = Node.new(9)
child_r = Node.new(20)
grand_child_r_l = Node.new(15)
grand_child_r_r = Node.new(7)
grand_child_l_l = Node.new(33)
child_r.left = grand_child_r_l
child_r.right = grand_child_r_r
child_l.left = grand_child_l_l
root.right = child_r
root.left = child_l

This tree can be illustrated by the image below.

DFS (Depth-first search)

def dfs(node)
p node.val
children = [node.left, node.right].compact children.each do |child|
dfs(child)
end
end
dfs(root)

Output is next:

3
9
33
20
15
7

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)

def bfs(node)
queue = []
queue.push(node)
while(queue.size != 0)
node = queue.shift
p node.val
children = [node.left, node.right].compact children.each do |child|
queue.push(child)
end
end
end
bfs(root)

Result:

3
9
20
33
15
7

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 the root of a binary tree, return its maximum depth.A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Given an example B-tree:

Ruby Solution

def max_depth(root)
return 0 if root.nil?
queue = [root]
depth = 0
while !queue.empty?
for i in 0..queue.length - 1
node = queue.shift
queue.push(node.left) if node.left
queue.push(node.right) if node.right
end
depth += 1
end
depth
end

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

--

--

Kirill Shevchenko

Software Engineer. Interested in Microservices, Distributed Systems and Cloud Services.