BFS and DFS algorithms 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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kirill Shevchenko

Kirill Shevchenko

244 Followers

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