# frozen_string_literal: true

class Tree
  attr_reader :data, :children

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

# The "Leafs" of a tree, elements that have no children
deep_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, [deep_fifth_node, eleventh_node])
seventh_node = Tree.new(7, [sixth_node])
shallow_fifth_node = Tree.new(5, [ninth_node])

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



# What we expect to see:
# 2 -> 7 -> 6 -> 5
# 11
# 5 -> 9 -> 4
def depth_first_search(node, target, unvisited=[])
  return node if node.data == target
  print("#{node.data} -> ") # print debugging output
  return if node.children.empty? && unvisited.empty?

  if node.children.count == 0
    puts # newline in output
    child = unvisited.pop
    depth_first_search(child, target, unvisited)
  elsif node.children.count == 1
    child = node.children.first
    depth_first_search(child, target, unvisited)
  elsif node.children.count > 1
    child = node.children.first
    unvisited.push(*node.children[1..-1])
    depth_first_search(child, target, unvisited)
  end
end

depth_first_search(trunk, 22) # => nil
# >> 2 -> 7 -> 6 -> 5 ->
# >> 11 ->
# >> 5 -> 9 -> 4 ->

depth_first_search(trunk, 9) # => #<Tree:0x007fbe340788d0 @data=9, ...>
# >> 2 -> 7 -> 6 -> 5 ->
# >> 11 ->
# >> 5 ->



# What we expect to see:
# 2 ->
# 7 -> 5
# 6 -> 9
# 5 -> 11 -> 4
def bfs(nodes, target)
  search_list = Array(nodes)
  return if search_list.empty?
  next_search_list = []

  search_list.each do |node|
    print("#{node.data} -> ")
    return node if node.data == target
    next_search_list.push(*node.children)
  end

  puts # for debugging output
  bfs(next_search_list, target)
end

bfs(trunk, 999) # => nil
# >> 2 ->
# >> 7 -> 5 ->
# >> 6 -> 9 ->
# >> 5 -> 11 -> 4 ->

bfs(trunk, 9) # => #<Tree:0x007f9aef84d438 @data=9, ...>
# >> 2 ->
# >> 7 -> 5 ->
# >> 6 -> 9 ->