dfs.rb

# In the above example it will check to see if the payload is 11 in the following order: 2, 7, 6, 5 when
# it gets to 5 and 5 has no children, it will return to the 6 and go to any children 6 has. 6 has a
# remaining child, which is 11 so that node is checked and since that value is the correct value it
# will be returned and searching will stop.

class Tree
    attr_accessor :payload, :children

    def initialize(payload, children)
        @payload = payload
        @children = children
    end

end


# The "Leafs" of a tree, elements that have no children
fifth_node    = Tree.new(5, [])
eleventh_node = Tree.new(11, [])
fourth_node   = Tree.new(4, [])


# The "Branches" of the tree
ninth_node = Tree.new(9, [fourth_node])
sixth_node = Tree.new(6, [fifth_node, eleventh_node])
seventh_node = Tree.new(7, [sixth_node])
fifth_node = Tree.new(5, [ninth_node])

# The "Trunk" of the tree
trunk = Tree.new(2, [seventh_node, fifth_node])

def depth_first_search(value, node)
  r = nil
  i = 0
  childrens = node.children || []
  size = childrens.length

  if node.payload == value
    puts "Destination Node #{node.payload}"
    node.payload
  else
    puts "Looking in Node #{node.payload}"
    while i < size && !r
      x = node.children[i]
      r = depth_first_search(value, x)
      i += 1
    end
    r
  end
end

# puts depth_first_search(9, trunk).inspect
# puts depth_first_search(11, sixth_node).inspect
# puts depth_first_search(9, trunk).inspect

puts depth_first_search(11, trunk).inspect