Basic BinaryTree class

BinaryTree.rb

#!/usr/bin/ruby

class BinaryTree
  include Enumerable
  attr_accessor :key, :data, :left, :right

  def initialize(h) # assume h is form {:key => k, :data=>d}
   @key = @data = nil
   assign_key_data(h)
   @left = @right = nil
  end

  def assign_key_data(obj) 
    if obj.class == Hash
     if obj.has_key?(:key) 
       @key = obj[:key]
       @data = obj[:data]
     end
   end

  end
  
  def bfs(search) # Breadth First Search
    found = nil
    queue = []
    queue << self
    while !queue.empty? do
      node = queue.shift
      break if found = node.visit(search)
      queue << @left unless @left.nil?
      queue << @right unless @right.nil?
    end
    found
  end

  def visit(search)
    found = nil
    if search.has_key?(:key)
      found = self if search == @key
    elsif search.has_key?(:data)
      found = self if search == @data
    end
    found
  end

  def is_bst?
    last = nil
    valid = true
    keys = self.keys_in_order
    keys.each_index do |i| 
      valid = keys[i] > keys[i-1] if i > 0 
      break if !valid
    end
    valid
  end
    
  def empty?
   (@left = nil && @right = nil)
  end
  
  def size
    count = 1
    count += @left.size unless @left.nil?
    count += @right.size unless @right.nil?
    count
  end
  
  def each(&block)
     @left.each(&block) unless @left.nil?
     yield @key
     @right.each(&block) unless @right.nil?
  end  
  

  def find(k)
    found = (@key == k) ? self : nil
    if match.nil?
     found = @left.find(k) if k < @key && !@left.nil?
     found = @right.find(k) if k > @key && !@right.nil?
    end
    found
  end  

  def pre_order(nodes = [])
    nodes << self
    @left.in_order(nodes) unless @left.nil?
    @right.in_order(nodes) unless @right.nil?
    nodes
  end  

  def in_order(nodes = [])
    @left.in_order(nodes) unless @left.nil?
    nodes << self
    @right.in_order(nodes) unless @right.nil?
    nodes
  end

  def post_order(nodes = [])
    @left.in_order(nodes) unless @left.nil?
    @right.in_order(nodes) unless @right.nil?
    nodes << self
    nodes   
  end
  
  def keys_in_order(keys = [])
    @left.in_order(keys) unless @left.nil?
    keys << self.key
    @right.in_order(keys) unless @right.nil?
    keys
  end

  def min_val
   min = nil
   if @left.nil?
    min = {:key => @key, :data => @data}
   else
     min = @left.min_val
   end
   min
  end

  def update(key, data)
    if node = find(key)
     node.data = data
    else 
     nil
    end
  end

  def << obj
   if obj.class == Hash
     if obj.has_key?(:key) 
       insert(obj)
     end 
   end
  end

  def insert(obj)
   if obj[:key] < @key
    @left  = push_or_attach(obj, @left)
   elsif obj[:key] > @key
    @right = push_or_attach(obj, @right)
   end

  end 

  def push_or_attach(obj, node)
    if node.nil?
      ### TODO: Check if :key and :data exist in obj and that obj is a Hash
      node = BinaryTree.new(obj)
    else
      node << obj
    end
    node
  end
    
  def print(level = 0, args*)
   options  = args.extract_options!
   if options.has_key?(:inorder) || options.empty?
    @left.print(level+1,options) unless @left.nil?
    puts "#{@key} "
    @right.print(level+1,options) unless @right.nil?
   elsif options.has_key?(:preorder)
    puts "#{@key} "
    @left.print(level+1,options) unless @left.nil?
    @right.print(level+1,options) unless @right.nil?
   elsif options.has_key?(:postorder)
    @left.print(level+1,options) unless @left.nil?
    @right.print(level+1,options) unless @right.nil?
    puts "#{@key} "
   end
  end
 
  def remove(key, parent = nil)
    result = nil
    if @key > key
      result =  @left.remove(key, self) unless @left.nil?
    elsif @key < key
      result = @right.remove(key,self) unless @right.nil?
    else
      rearrange(key, parent)
    end 
   result
  end

  def rearrange(key, parent)
    if !@left.nil? && !@right.nil?
      min = @right.min_val
      @key,@data = min[:key], min[:data]
      right.remove(@key, self)
    elsif parent.left == self
      parent.left = (!@left.nil?) ? @left : @right
    elsif parent.right == self
      parent.right = (!@left.nil?) ? @left : @right
    end
  end

end

Binary Search Tree in Ruby