class Node
  attr_accessor :left_child, :right_child, :value

  def initialize(value)
    @value = value
    @left_child = nil
    @right_child = nil
  end

  #inserts a value to the tree at the right place
  def insert(value)
    if value < @value
      if not @left_child.nil? then @left_child.insert(value) else @left_child = Node.new(value) end
    else
      if not @right_child.nil? then @right_child.insert(value) else @right_child = Node.new(value) end
    end
  end

  #searches the tree recursivly for a value
  def search(value)
    return value if value == @value
    if value < @value then @left_child.search(value) else @right_child.search(value) end
  end

  #uberpwnage depth method. calculates the depth of the tree recursively
  def depth
    [@left_child.depth, @right_child.depth].max+1
  end

  #searches the tree for the minimum value
  def min_value
    if @left_child.nil? then value else @left_child.min_value end
  end

  #lolmethod calculating the size of the tree
  def size
    @left_child.size + @right_child.size + 1
  end

  def print_tree

  end

  #helper methods to get some freakin code, oh jeah baby
  def nil.depth
    0
  end

  def nil.size
    0
  end
end

require "node.rb"
#class that represents a binary tree with methods to access
class BinaryTree
  attr_accessor :root, :size
  def initialize

  end

  #insert values to the tree and creates root node if it does not exist
  def insert(value)
    if not @root.nil? then @root.insert(value) else @root = Node.new(value) end
  end

  #returns the first value of the tree that has the same value as the argument value
  def search(value)
    @root.search(value)
  end

  def size
    @root.size
  end

  #return the depth of the tree
  def depth
    @root.depth if not @root.nil?
  end

  #returns the minimum value of the tree (the node most left)
  def min_value
    @root.min_value if not @root.nil?
  end

  def print_tree
    @root.print_tree if not @root.nil?
  end

end

require "binary_tree"


btree = BinaryTree.new

#testarrays
array = [5, 1, 3, 4, 7, 8, 4, 4, 4]
array2 = [5, 1, 7]
array3 = [5, 1, 3, 4, 7, 8]

puts "Binary Tree"
puts "InputArray: #{array}"
puts "InputArraySize: #{array.length}"

#inserting the testvalues
array.each do |value|
  btree.insert(value)
end

puts "================================"
puts "binary tree created"
puts "BinaryTreeSize: #{btree.size}"
puts "BinaryTreeDeapth: #{btree.depth}"
puts "BinaryTreeMinimumValue: #{btree.min_value}"
puts "================================"
puts btree.search(3)