# 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:

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

enddfs(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

endbfs(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, returnits maximum depth.A binary tree'smaximum depthis 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.