Printing out Breadth First Search using Ruby

Question

Exploring various examples via the Web, I cannot seem to implement printing my binary tree with a breadth first example. I'm given a hint with children=nil within #printf(children=nil), but cannot get anything going. I'm provided the idea of created a queue array or two, but my particular function is not performing a search or passing in any argument. I simply want to print my tree from top node on down.

Output of binary tree

=> #<BinarySearchTree:0x007fbe40b044c8 @root=#<Node:0x007fbe40b044f0 @title="The Matrix", @rating=87, @parent=nil, @left=#<Node:0x007fbe40b04478 @title="Pacific Rim", @rating=72, @parent=#<Node:0x007fbe40b044f0 ...>, @left=nil, @right=#<Node:0x007fbe40b04428 @title="Braveheart", @rating=78, @parent=#<Node:0x007fbe40b04478 ...>, @left=nil, @right=nil>>, @right=#<Node:0x007fbe40b042e8 @title="District 9", @rating=90, @parent=#<Node:0x007fbe40b044f0 ...>, @left=nil, @right=#<Node:0x007fbe40b04298 @title="The Shawshank Redemption", @rating=91, @parent=#<Node:0x007fbe40b042e8 ...>, @left=nil, @right=nil>>>>

output of function SHOULD look like:

The Matrix: 87
Pacific Rim: 72
District 9: 90
Braveheart: 78
Shawshank: 91
...

my print function

def printf(children=nil)
  current = @root
  queue = [current]

  if current.left && current.right
    queue << current.left << current.right
    puts queue.methods.sort
  elsif current.right
    queue << current.right
  end

  queue.each do |i|
    #print out my created array
  end
end

Puzzled of how to move through my binary tree object given this particular example and what I have now won't work, especially as the tree expands. Ideas or advice?

Answer 1

Level order traversal in Tree is inspired by BFS of Graph, in level order we use queue to traverse through the tree and keep pushing left and right nodes until the queue is empty or the node is found(if we're searching for one). Here is a typical example of the same:

def bfs(node)
  return nil if node.nil? || root.nil? # nothing to do if there is no node or root to begin the search
  queue = Queue.new
  queue.enq(root)
  result = nil
  while !queue.empty?
    value = queue.deq
    if value.title == node.title && value.rating == node.rating
      result = value
      break
    end

    # keep moving the levels in tree by pushing left and right nodes of tree in queue
    queue.enq(value.left) if value.left
    queue.enq(value.right) if value.right
  end

  result # returns node found in BST else default value nil
end

Assuming that root is a getter method in your BST class. Class Queue is available in Ruby using thread. You might have to do require 'thread' in your code to have it available in your code.

Time Complexity: O(n)

Space Complexity: O(n) for queue.

Answer 2

modified from above

  def printf(node)
    return nil if node.nil?
    queue = Queue.new
    queue.enq(node)
    result = nil
    while !queue.empty?
      value = queue.deq
      puts value.title if !value.title.nil?
      # keep moving the levels in tree by pushing left and right nodes of tree in queue
      queue.enq(value.left) if value.left
      queue.enq(value.right) if value.right
    end
  end