Breadth First Search Algorithm using Binary Tree

bfs.rb

# We would use binary tree to implement Breadth First Search(BFS)
# use Queue to help implement BFS, we use "deq" to remove an element and "enq" to add element
# 1. Add root node to the queue, and mark it as visited(already explored).
# 2. Loop on the queue as long as it's not empty.
#    1. Get and remove the node at the top of the queue(current).
#    2. For every non-visited child of the current node, do the following: 
#       1. Mark it as visited.
#       2. Check if it's the goal node, If so, then return it.
#       3. Otherwise, push it to the queue.
# 3. If queue is empty, then goal node was not found!


class BinaryTree
  attr_reader :value
  attr_accessor :left, :right

  def initialize(value)
    @value = value
    @left =nil
    @right =nil
  end
  
  def bfs(node)
    queue = Queue.new
    queue.enq(self) # add the root node into the queue 
    visited = []

    while !queue.empty? # iterate while the queue is not empty.
      current_node = queue.deq
      visited << current_node
	    
      # return search node
      if current_node.value == node.value
	return current_node
      end
      
      # add left and right children into the queue (if the current node has children)
      if current_node.left && !visited.include?(current_node.left)
        queue.enq(current_node.left)
      end

      if current_node.right && !visited.include?(current_node.right)
        queue.enq(current_node.right)
      end 
    end
  end
end