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.

class Node
attr_accessor :val, :left, :right
def initialize(val)
@val = val
@left, @right = nil, nil
end
end
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

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)
3
9
33
20
15
7

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)
3
9
20
33
15
7

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.
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

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