An implementation of a binary search tree data structure, in Ruby.

binary_search_tree.rb

module BinarySearchTree
  class Node

    attr_reader :value
    attr_accessor :left, :right, :count

    def initialize(v)
      @value = v
      @count = 1
    end

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

    def to_a
      left.to_a + Array.new(@count, value) + right.to_a
    end

    def min
      left.nil? ? value : left.min
    end

    def max
      right.nil? ? value : right.max
    end

    private

    def insert_left(v)
      left ? left.insert(v) : @left = Node.new(v)
    end

    def insert_right(v)
      right ? right.insert(v) : @right = Node.new(v)
    end
  end
end


# Example:

tree = BinarySearchTree::Node.new(100)
tree.insert(35)
tree.insert(60)
tree.insert(234)
tree.insert(60)

puts "Min.: #{tree.min}\n" # => 35
puts "Max.: #{tree.max}\n" # => 234
puts "Sorted:\n"
puts tree.to_a # => 35, 60, 60, 100, 234