# 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  endend`

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_lchild_r.right = grand_child_r_rchild_l.left = grand_child_l_lroot.right = child_rroot.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)  endenddfs(root)`

Output is next:

`393320157`

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.

`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  endendbfs(root)`

Result:

`392033157`

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  depthend`

Here we are calculating depth by incrementing the variable for each breadth iteration.