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