Breadth First Search and Depth First Search binary tree

Ruby
1

Hi. My full code is posted below. I have a DFS and a BFS method inside
the BTreeBuilder class. I’m pretty sure the BFS correct, but I’m not so
sure about the DFS and can’t find any examples online.

My question is, is the Depth_First_Search method correct?

Thanks a bunch guys.

class Node

attr_accessor :value, :left_child, :right_child

def initialize(value)
@value = value
end
end

class BTreeBuilder

attr_accessor :root

def initialize(root = nil)
@root = Node.new(root)
end

def build_tree(array)
if @root.value.nil?
@root = Node.new(array.shift)
end
array.each do |n|
insert_node(n, @root)
end
end

def insert_node(value, node)
if value < node.value
if node.left_child.nil?
node.left_child = Node.new(value)
else
insert_node(value, node.left_child)
end
elsif value > node.value
if node.right_child.nil?
node.right_child = Node.new(value)
else
insert_node(value, node.right_child)
end
else
puts “There was a duplicate ‘#{value}.’ Only one instance is
included!”
end
end

def breadth_first_search(item)
queue = [@root]

while !queue.empty?
  current_node = queue.shift
  return current_node if current_node.value == item
  queue.unshift(current_node.left_child) if

!current_node.left_child.nil?
queue.unshift(current_node.right_child) if
!current_node.right_child.nil?
end
puts “Item not found”
return nil
end

def depth_first_search(item)
stack = [@root]

while !stack.empty?
  current_node = stack.pop
  return current_node if current_node.value == item

  stack << current_node.left_child if

!current_node.left_child.nil?
stack << current_node.right_child if
!current_node.right_child.nil?
end
puts “Item not found”
return nil
end

def dfs_rec(item, node = @root)

return nil if node.nil?
return node if node.value == item

left_node = dfs_rec(item, node.left_child)
right_node = dfs_rec(item, node.right_child)

end

end

array = [5,3,4,6,1,99,100,45,63]
tree = BTreeBuilder.new
tree.build_tree(array)