Little spike on Tree implementation with EmptyNode as a NullObject

empty_node.rb

class Tree
  class << ( EmptyNode = Object.new )
    def upsert(parent, side, new_child)
      parent.send("#{side}=", new_child)
      parent
    end

    def contains?(*)
      false
    end
  end

  class Node
    include Comparable

    def initialize(value)
      @value = value
      @left = EmptyNode
      @right = EmptyNode
    end

    attr_accessor :value, :left, :right

    def contains?(value)
      if self.value == value
        true
      elsif self.value > value
        self.left.contains? value
      else
        self.right.contains? value
      end
    end

    def insert(child, side=nil)
      if self >= child
        self.left.upsert self, :left, child
      else
        self.right.upsert self, :right, child
      end
    end

    def upsert(parent, side, new_child)
      self.insert new_child
    end

    def <=>(other)
      self.value <=> other.value
    end
  end
end

@sandersch, Tree has no behavior? Does that mean it is a module?

It feels like there is a lot of knowledge of parent in the empty node on line four. What if it was parent.add_node(side, new_child) ?

Each node knows what is underneath him? Is this something that should be in the Tree? Maybe it is ok in the Node?

I like the whole thing. Do you have the tests you used?

Just saw the word spike?