Exploring Tree Algorithms with Ruby

traverse.rb

class Node

  @@visits = 0

  @@queue = []

  attr_accessor :value, :left_child, :right_child, :visited

  def self.count_visit
    @@visits += 1
  end

  def self.visits
    @@visits
  end

  def initialize(value)
    @value = value
  end

  def visit
    @visited = true
    p value
  end

  def find_depth_first(needle)
    Node.count_visit
    return self if value == needle
    if left_child
      result = left_child.find_depth_first(needle)
    end
    return result if result
    if right_child
      right_child.find_depth_first(needle)
    end
  end

  def traverse_breadth_first
    @@queue.push(self) unless visited
    while !@@queue.empty? do
      current = @@queue.first
      current.visit
      @@queue.push(current.left_child) if current.left_child
      @@queue.push(current.right_child) if current.right_child
      @@queue.shift()
    end


  end

end

# https://www.youtube.com/watch?v=86g8jAQug04&index=34&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P
#            F
#        D        J
#     B    E    G   K
#   A   C

root = Node.new('F')
root.left_child = Node.new('D')
root.left_child.left_child = Node.new('B')
root.left_child.left_child.left_child = Node.new('A')

root.right_child = Node.new('J')
root.left_child.right_child = Node.new('E')
root.left_child.left_child.right_child = Node.new('C')
root.right_child.left_child = Node.new('G')
root.right_child.right_child = Node.new('K')

root.traverse_breadth_first

#result = root.find_depth_first('K')
#p result.nil? ? "not found!" : "found #{result.value}"
#p "visits: #{Node.visits}"