ruby BinaryTree implemention

binary_tree.rb

# https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html
module BinaryTree
  class Node
    attr_accessor :value, :left, :right, :parent
    def initialize(v, parent = nil)
      @value = v
      @left  = EmptyNode.new(self)
      @right = EmptyNode.new(self)
      @parent = parent
    end

    def empty?
      false
    end

    def size
      size =  1
      size += left.size
      size += right.size
      size
    end

    def insert(v)
      case value <=> v
      when 1  then insert_left(v)
      when -1 then insert_right(v)
      when 0  then false
      end
    end

    def depth(v)
      case value <=> v
      when 1  then 1 + left.depth(v)
      when -1 then 1 + right.depth(v)
      when 0  then 1
      end
    end

    def height
      height = 1
      height += [left.height, right.height].max
      height
    end

    def max
      right.max
    end

    def min
      left.min
    end

    def values_on_depth(n)
      return [value] if n == 1
      left.values_on_depth(n - 1).concat(right.values_on_depth(n-1))
    end

    def inspect
      "(#{value}::#{left.inspect}|#{right.inspect})"
    end

    def include?(v)
      case value <=> v
      when 1  then left.include?(v)
      when -1 then right.include?(v)
      when 0  then true
      end
    end

    def replace_and_delete(v)
      case [left.empty?, right.empty?]
      when [true, false] , [false, true]
        self.parent.right = self.left
      when [true, true]
        self.parent.left  = EmptyNode.new(self.parent)
        self.parent.right = EmptyNode.new(self.parent)
      else
        left_max   = left.max
        self.value = left_max
        left.delete(left_max)
      end
    end

    def delete(v)
      case value <=> v
      when 1  then left.delete(v)
      when -1 then right.delete(v)
      when 0  then replace_and_delete(v)
      end
    end

    def to_a(mode=:pre_order)
      mode = %W{pre_order in_order post_order}.include?(mode.to_s) ? mode : :pre_order
      self.send(mode.intern)
    end

    def pre_order
      [self.value].concat(left.pre_order).concat(right.pre_order)
    end

    def in_order
      left.in_order.concat([self.value]).concat(right.in_order)
    end

    def post_order
      left.post_order.concat(right.post_order).concat([self.value])
    end

    private

    def insert_left(v)
      left.insert(v) || self.left = Node.new(v, self)
    end

    def insert_right(v)
      right.insert(v) || self.right = Node.new(v, self)
    end
  end

  class EmptyNode
    attr_accessor :parent
    def initialize(v)
      @parent = v
    end

    def include?(*)
      false
    end

    def insert(*)
      false
    end

    def inspect(*)
     "{}"
    end

    def empty?
      true
    end

    def depth(*)
      0
    end

    def height
      0
    end

    def size
      0
    end

    def delete(*)
      false
    end

    def max(*)
      parent.value
    end

    def min(*)
      parent.value
    end

    def values_on_depth(*)
      []
    end

    def pre_order
      []
    end

    def in_order
      []
    end

    def post_order
      []
    end
  end
end

nd = BinaryTree::Node.new(8)

[3, 1, 5, 4, 9, 12, 11].each do |t|
  nd.insert(t)
end

puts nd.inspect
nd.delete(8)
puts nd.inspect
puts nd.max
puts nd.min
puts "-----------------------"
puts nd.values_on_depth(1).join(", ")
puts nd.values_on_depth(2).join(", ")
puts nd.values_on_depth(3).join(", ")
puts nd.values_on_depth(4).join(", ")

# nd2 = BinaryTree::Node.new(8)
# [5, 4, 9, 7, 11, 1, 12, 3, 2].each do |t|
#   nd2.insert(t)
# end

puts "-----------------------"
puts nd.pre_order.join(', ')
puts "-----------------------"
puts nd.in_order.join(', ')
puts "-----------------------"
puts nd.post_order.join(', ')

puts nd.size
puts nd.to_a.join(', ')