# We would use a binary tree to implement Breadth First Search(BFS)
# We could use a shift or push to add a remove from an array or
# we use queue to help implement BFS, we use "deq" to remove an node and "enq" to add node
# 1. Add root node to the queue, and mark it as visited.
# 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 destination node, If so, then return it.
#       3. Otherwise, push it to the queue.
# 3. If queue is empty, then destination node was not found!

class BinaryTree
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end

  # use this method to build the binary tree
  # This method inside children node to the left of a node
  def insert_left(value)
    if self.left.nil?
      self.left = BinaryTree.new(value)
    else
      new_node =  BinaryTree.new(value)
      new_node.left = self.left
      self.left = new_node
    end
  end

  # use this method to build the binary tree
  # This method inside children node to the right of a node
  def insert_right(value)
    if self.right.nil?
      self.right = BinaryTree.new(value)
    else
      new_node =  BinaryTree.new(value)
      new_node.right = self.right
      self.right = new_node
    end
  end
end

def bread_first_search(node)
  queue = Queue.new
  queue.enq(node) # enqueue origin node
  visited = []

  while !queue.empty?
    current_node = queue.deq
    visited << current_node # make current node as visited

    if current_node.value == node.value
      return current_node . # return node if is the destination node
    end

    if current_node.left && !visited.include?(current_node.left)
      queue.enq(current_node.left) #enqueue the node to the left of the current node
    end

    if current_node.right && !visited.include?(current_node.right)
      queue.enq(current_node.right) #enqueue the node to the right of the current node
    end
  end
end

### Create a binary tree
a_node = BinaryTree.new('a')
a_node.insert_left('b')
a_node.insert_right('c')

b_node = a_node.left
b_node.insert_right('d')

c_node = a_node.right
c_node.insert_left('e')
c_node.insert_right('f')

e_node = c_node.left
f_node = c_node.right

p bread_first_search(a_node)