breadth_first_search.rb

# 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
  end
end

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

  until queue.empty?
    current_node = queue.deq
    visited << current_node # mark current node as visited

    if current_node.value == value
      return "Found the destination node #{current_node.value}" # return 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
  "Can't find node with the value #{value}"
end

### Create a binary tree
def tree
  BinaryTree.new(5).tap do |t|
    t.left = BinaryTree.new(3)
    t.right = BinaryTree.new(8)
    t.left.left = BinaryTree.new(1)
    t.left.right = BinaryTree.new(7)
  end
end

p bread_first_search(tree, 8) # => Found the destination node 8
p bread_first_search(tree, 14) # => Can't find node with the value 14