# Binary-Search-Tree Implementation
# Jungtaek Lim(Heart), 2009-03-04

class BinarySearchTreeNode
  attr_accessor :left_child, :right_child, :key, :value

  def initialize
    @left_child = nil
    @right_child = nil
    @key = nil
    @value = nil
  end

end

class BinarySearchTree
  
  def initialize
    @root = nil
  end

  def insert_node(key, value)
    node = BinarySearchTreeNode.new

    node.key = key
    node.value = value

    if nil == @root
      @root = node
      
      return node
    else
      parent_node = find_place_for_insert(@root, key)

      return nil if nil == parent_node

      if parent_node.key > key
        parent_node.left_child = node
      else
        parent_node.right_child = node
      end

      return node
    end
  end

  def delete_node(key)
    delete_node(@root, key)
  end

  def delete_node(root_node, key)
    node = find_node(root_node, key)

    return nil if nil == node

    parent_node = find_parent_node(root_node, node.key)

    degree = 0
    degree += 1 unless nil == node.left_child
    degree += 1 unless nil == node.right_child

    case degree
    when 0
      if nil == parent_node       # @root == node
        @root = nil
        
        return
      end
      
      if parent_node.left_child == node
        parent_node.left_child = nil
      else
        parent_node.right_child = nil
      end
      
    when 1
      if nil == parent_node       # @root == node
        if nil != node.left_child
          @root = node.left_child
        else
          @root = node.right_child
        end

        return
      end

      child_node = (nil != node.left_child ? node.left_child : node.right_child)

      if parent_node.left_child == node
        parent_node.left_child = child_node
      else
        parent_node.right_child = child_node
      end

    when 2
      highest_node_left_subtree = find_highest_key_node(node.left_child)

      node.key = highest_node_left_subtree.key
      node.value = highest_node_left_subtree.value
      
      delete_node(node.left_child, highest_node_left_subtree.key)
    end
    
  end

  def find_node(key)
    return find_node(@root, key)
  end

  def find_parent_node(key)
    return nil if @root.key == key
    
    return find_parent_node(@root, key)
  end
  
  def inorder_traversal
    travel_list = []

    inorder_traversal_recursive(travel_list, @root) unless @root == nil

    return travel_list
  end

  private

  def find_node(node, key)
    return nil if nil == node

    if node.key == key
      return node
    elsif node.key > key
      return find_node(node.left_child, key)
    else
      return find_node(node.right_child, key)
    end

  end

  def find_parent_node(node, key)
    return nil if nil == node

    return node if node.left_child != nil && node.left_child.key == key

    return node if root_node.node != nil && node.right_child.key == key

    if node.key > key
      return find_parent_node(node.left_child, key)
    else
      return find_parent_node(node.right_child, key)
    end

  end

  def find_place_for_insert(node, key)
    return nil if nil == node

    if node.key == key
      return nil
    elsif node.key > key
      return node if nil == node.left_child

      return find_place_for_insert(node.left_child, key)
    else
      return node if nil == node.right_child

      return find_place_for_insert(node.right_child, key)
    end
  end

  def find_highest_key_node(node)
    return nil if nil == node

    highest_key_node = node

    while nil != highest_key_node.right_child
      highest_key_node = highest_key_node.right_child
    end

    return highest_key_node
  end

  def inorder_traversal_recursive(travel_list, node)
    return if node == nil

    inorder_traversal_recursive(travel_list, node.left_child)
    travel_list.push(node)
    inorder_traversal_recursive(travel_list, node.right_child)

  end
end

def print_travel_node_list(travel_list)
  print '[ '

  travel_list.each do |node|
    print node.key.to_s + "(" + node.value.to_s + ")"
    print " "
  end

  puts ']'
end

def make_example_bst
  bst = BinarySearchTree.new
  bst.insert_node(8, 1)
  bst.insert_node(3, 2)
  bst.insert_node(10, 3)
  bst.insert_node(2, 4)
  bst.insert_node(5, 5)
  bst.insert_node(14, 7)
  bst.insert_node(11, 12)
  bst.insert_node(16, 13)

  return bst
end

bst = make_example_bst
print_travel_node_list bst.inorder_traversal
bst.insert_node(4, 10)
print_travel_node_list bst.inorder_traversal

puts "Found 4" if nil != bst.find_node(4)
puts "Found 9" if nil != bst.find_node(9)

bst = make_example_bst
bst.delete_node(5)

print_travel_node_list bst.inorder_traversal

bst = make_example_bst
bst.delete_node(10)

print_travel_node_list bst.inorder_traversal

bst = make_example_bst
bst.delete_node(8)

print_travel_node_list bst.inorder_traversal