BFS and DFS algorithms in Ruby

Tree

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

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.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

7 Promising VS Code Extensions Introduced in 2021

Image of StackOverFlow Developer Survey 2021 best IDE — VS Code

Everything about Load Balancer with Cheat Sheet

Ravencoin Mining for beginners

Ravencoin Mining for Beginners

MongoDB: watch your pipeline

Writing CTFd plugins: a beginner walkthrough

Software Versions Explained

Data Type Of JVM

Digital Analytics Review — Week 10

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

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

More from Medium

Controlling the Return

The Best Ruby Enumerables

Learning a new programming language after successfully learning the first one…

Explaining Active Record like a Broken Record