class BinaryTreeNode
  attr_accessor :left_child, :right_child, :parent, :data

  def initialize(data)
    @left_child = @right_child = @parent = nil
    @data = data
  end
end

class DigitalSearchTree
  def initialize
    @root = nil

  end

  # assume field is 5 bit
  def insert(data)
    node = BinaryTreeNode.new(data)
    offset = data[0] - 'A'[0] + 1

    mask = 0b10000

    if !@root
      @root = node
      return true
    end

    node_ptr = @root

    begin
      bit = offset & mask

      if node_ptr.data == node.data
        p "Already found"
        return false
      end

      if bit == 0
        if !node_ptr.left_child
          node_ptr.left_child = node
          node.parent = node_ptr
          return true
        end

        node_ptr = node_ptr.left_child
      else  # bit > 0
        if !node_ptr.right_child
          node_ptr.right_child = node
          node.parent = node_ptr
          return true
        end

        node_ptr = node_ptr.right_child
      end

      mask = mask >> 1
    end while mask > 0

    return false
  end

  def delete(data)
    target_node = search(data)

    return nil if !target_node

    if @root == target_node
      @root = nil

      return target_node
    end

    parent_node = target_node.parent

    is_target_left_child = (parent_node.left_child == target_node)

    if !target_node.left_child && !target_node.right_child
      # if node has no child
      if is_target_left_child
        parent_node.left_child = nil
      else
        parent_node.right_child = nil
      end

    elsif target_node.left_child && !target_node.right_child
      # node has left child
      if is_target_left_child
        parent_node.left_child = target_node.left_child
        parent_node.left_child.parent = parent_node
      else
        parent_node.right_child = target_node.left_child
        parent_node.right_child.parent = parent_node
      end

    elsif !target_node.left_child && target_node.right_child
      # node has right child
      if is_target_left_child
        parent_node.left_child = target_node.right_child
        parent_node.left_child.parent = parent_node
      else
        parent_node.right_child = target_node.right_child
        parent_node.right_child.parent = parent_node
      end
    else
      # node has both children

      # move node's right child to node's left_child's right child
      target_node.left_child.right_child = target_node.right_child
      target_node.right_child.parent = target_node.left_child

      # at now, assume node has only left child
      if is_target_left_child
        parent_node.left_child = target_node.left_child
        parent_node.left_child.parent = parent_node
      else
        parent_node.right_child = target_node.left_child
        parent_node.right_child.parent = parent_node
      end
      
    end

    return target_node

  end

  # assume field is 5 bit
  def search(data)
    offset = data[0] - 'A'[0] + 1

    mask = 0b10000

    return nil if !@root

    node_ptr = @root

    begin
      bit = offset & mask

      return node_ptr if node_ptr.data == data

      if bit == 0
        return nil if !node_ptr.left_child
          
        node_ptr = node_ptr.left_child
      else  # bit > 0
        return nil if !node_ptr.right_child

        node_ptr = node_ptr.right_child
      end

      mask = mask >> 1
    end while mask > 0

    return nil
  end

  def inorder_traversal
    travel_list = []

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

    return travel_list
  end

  private

  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.data.to_s
    print " "
  end

  puts ']'
end


dst = DigitalSearchTree.new

dst.insert('A')
dst.insert('S')
dst.insert('E')
dst.insert('R')
dst.insert('C')
dst.insert('H')
dst.insert('X')
dst.insert('X')
puts "------------------------------"

traversal_list = dst.inorder_traversal
print_travel_node_list traversal_list

puts "------------------------------"
puts dst.search('B') != nil
puts dst.search('E') != nil
puts dst.search('X') != nil
puts dst.search('F') != nil
puts "------------------------------"

dst.delete('H')
puts dst.search('H') != nil
puts dst.search('C') != nil
puts "------------------------------"

dst.delete('E')
puts dst.search('E') != nil
puts dst.search('C') != nil
puts "------------------------------"

dst.delete('S')
puts dst.search('S') != nil
puts dst.search('X') != nil
puts dst.search('R') != nil
puts "------------------------------"

traversal_list = dst.inorder_traversal
print_travel_node_list traversal_list
puts "------------------------------"

"Already found"
------------------------------
[ C E H A R S X ]
------------------------------
false
true
true
false
------------------------------
false
true
------------------------------
false
true
------------------------------
false
true
true
------------------------------
[ C A R X ]
------------------------------