# frozen_string_literal: true
#=> nil

class Node
  attr_accessor :item, :left, :right
  def initialize(item)
    @item = item
    @left = nil
    @right = nil
  end
end
#=> :initialize

def insert_node(node, ele)
  return Node.new(ele) if node.nil?
  
  if ele < node.item
    node.left = insert_node(node.left, ele)
    else
    node.right = insert_node(node.right, ele)
  end
  node
end
#=> :insert_node

def delete_node(node, val)
  return nil if node.nil?
  
  if val < node.item
    node.left = delete_node(node.left, val)
    elsif val > node.item
    node.right = delete_node(node.right, val)
    else
    return nil if node.left.nil? && node.right.nil?
    
    min_larger_right = find_min(node.right)
    node.item = min_larger_right.item
    node.right = delete_node(node.right, min_larger_right.item)
  end
  node
end
#=> :delete_node

def find_min(node)
  node = node.left while node.left
  node
end
#=> :find_min

def make_binary_tree(data)
  btree = nil
  data.each do |ele|
    btree = insert_node(btree, ele)
  end
  btree
end
#=> :make_binary_tree

def print_with_inorder(btree)
  return if btree.nil?
  
  print_with_inorder(btree.left)
  puts btree.item
  print_with_inorder(btree.right)
end
#=> :print_with_inorder

def inorder_to_array(btree)
  return [] if btree.nil?
  
  inorder_to_array(btree.left) + [btree.item] + inorder_to_array(btree.right)
end
#=> :inorder_to_array
data = 3.times.to_a.shuffle
#=> [0, 2, 1]

# make tree
#=> nil
btree = make_binary_tree(data)
#=> #<Node:0x00007faf2a155ca8
#...

# inorder
#=> nil
p inorder_to_array(btree)
[0, 1, 2]
#=> [0, 1, 2]

# insert
#=> nil
insert_node(btree, 123)
#=> #<Node:0x00007faf2a155ca8
# @item=0,
# @left=nil,
# @right=
  #<Node:0x00007faf2a155be0
   @item=2,
   @left=#<Node:0x00007faf2a155b68 @item=1, @left=nil, @right=nil>,
   @right=#<Node:0x00007faf2a30c600 @item=123, @left=nil, @right=nil>>>
p inorder_to_array(btree)
[0, 1, 2, 123]
#=> [0, 1, 2, 123]

# delete
#=> nil
delete_node(btree, 0)
#=> #<Node:0x00007faf2a155ca8
# @item=1,
# @left=nil,
# @right=
  #<Node:0x00007faf2a155be0
   @item=2,
   @left=nil,
   @right=#<Node:0x00007faf2a30c600 @item=123, @left=nil, @right=nil>>>
p inorder_to_array(btree)
[1, 2, 123]
#=> [1, 2, 123]