Implementing Binary Tree in Ruby

Question

I've been trying to implement BinaryTree class in Ruby, but I'm getting the stack level too deep error, although I don't seem to be using any recursion in that particular piece of code:

1.  class BinaryTree
2.    include Enumerable
3.      
4.      attr_accessor :value
5.      
6.      def initialize( value = nil )
7.          @value = value
8.          @left = BinaryTree.new  # stack level too deep here
9.          @right = BinaryTree.new # and here
10.     end
11.     
12.     def empty?
13.         ( self.value == nil ) ? true : false
14.     end
15.         
16.         def <<( value )
17.           return self.value = value if self.empty?
18. 
19.           test = self.value <=> value
20.           case test
21.             when -1, 0 
22.                 self.right << value
23.             when 1 
24.                 self.left << value
25.           end
26.         end     # <<
27.     
28.  end

Edit: My question has gone a little bit off track. The current code setting gives me the stack level too deep error at line 8. However, if I employ Ed S.'s solution

@left = @right = nil

then the << method complains saying: undefined method '<<' for nil:NilClass (NoMethodError) at line 22.

Could anyone suggest how to resolve this? My idea is that if I could somehow tell the BinaryTree class that variables left and right are of instances of BinaryTree (i.e. their type is BinaryTree) it would all be well. Am I wrong?

Answer 1

although I don't seem to be using any recursion in that particular piece of code:

Yet...

def initialize( value = nil )
    @value = value
    @left = BinaryTree.new  # this calls initialize again
    @right = BinaryTree.new # and so does this, but you never get there
end

That is infinite recursion. You call initilize, which in turn calls new, which in turn calls initialize... and around we go.

You need to add a guard in there to detect that you have already initialized the main node and are now initializing leafs, in which case, @left and @right should just be set to nil.

def initialize( value=nil, is_sub_node=false )
    @value = value
    @left = is_sub_node ? nil : BinaryTree.new(nil, true)
    @right = is_sub_node ? nil : BinaryTree.new(nil, true)
end

---

To be honest though... why aren't you just initializing left and right to nil to begin with? They don't have values yet, so what are you gaining? It makes more sense semantically; you create a new list with one element, i.e., elements left and right don't yet exist. I would just use:

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