7

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?

1
  • 2
    Every time you call BinaryTree.new, it hits the initialize method and calls another BinaryTree.new, and repeats forever. That's why your stack is overflowing
    – bigpotato
    Oct 13, 2014 at 14:44

4 Answers 4

13

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
9
  • I would just have one additional question to it. Is that a standard way to initialize attributes which are of type the class in which they appear? I'm not sure if I asked the right way.
    – Maputo
    Aug 30, 2012 at 20:52
  • @Maputo: Yes, you define a method named initialize and that is what is called when someone calls YourType.new. You should just set left and right to nil. It makes more sense and it solved the infinite recursion problem. Aug 30, 2012 at 20:54
  • If I do that, I'm getting than other problems with the << function which I'm overriding. Check out the source again please, I've just edited it.
    – Maputo
    Aug 30, 2012 at 20:56
  • @Maputo: Ok, so you have another error in your code, that doesn't mean your initial approach was correct. You're never assigning value, you simply call that method recursively over and over again. If you're going to use recursion you need a guard which determines when to stop, i.e., when to assign value and exit the process. Aug 30, 2012 at 20:58
  • 1
    @Maputo: You initialize them to nil. Variables aren't typed in Ruby, values are. Aug 30, 2012 at 21:11
2
1.  class BinaryTree
2.    include Enumerable
3.      
4.      attr_accessor :value
5.      
6.      def initialize( value = nil )
7.          @value = value
8.      end 
9.      
10.     def each # visit
11.         return if self.nil?
12.         
13.         yield self.value
14.         self.left.each( &block ) if self.left
15.         self.right.each( &block ) if self.right     
16.     end
17. 
18.     def empty?
19.         # code here
20.     end
21.         
22.     def <<( value ) # insert
23.         return self.value = value if self.value == nil
24. 
25.         test = self.value <=> value
26.         case test
27.             when -1, 0
28.                 @right = BinaryTree.new if self.value == nil
29.                 self.right << value
30.             when 1 
31.                 @left = BinaryTree.new if self.value == nil
32.                 self.left << value
33.         end
34.     end     # <<
35.  end
1

You might need to fix the infinite recursion in your code. Here's a working example of a binary tree. You need to have a base condition to terminate your recursion somewhere, else it'll be a stack of infinite depth.

Example of Self-Referential Data Structures - A Binary Tree

class TreeNode
  attr_accessor :value, :left, :right

  # The Tree node contains a value, and a pointer to two children - left and right 
  # Values lesser than this node will be inserted on its left
  # Values greater than it will be inserted on its right
  def initialize val, left, right
    @value = val
    @left = left
    @right = right
  end
end

class BinarySearchTree

  # Initialize the Root Node
  def initialize val
    puts "Initializing with: " + val.to_s
    @root = TreeNode.new(val, nil, nil)
  end

  # Pre-Order Traversal
  def preOrderTraversal(node = @root)
    return if (node == nil)
    preOrderTraversal(node.left)
    preOrderTraversal(node.right)
    puts node.value.to_s
  end

  # Post-Order Traversal
  def postOrderTraversal(node = @root)
    return if (node == nil)
    puts node.value.to_s
    postOrderTraversal(node.left)
    postOrderTraversal(node.right)
  end

  # In-Order Traversal : Displays the final output in sorted order
  # Display smaller children first (by going left)
  # Then display the value in the current node 
  # Then display the larger children on the right
  def inOrderTraversal(node = @root)
    return if (node == nil)
    inOrderTraversal(node.left)
    puts node.value.to_s
    inOrderTraversal(node.right)
  end

  # Inserting a value
  # When value > current node, go towards the right
  # when value < current node, go towards the left
  # when you hit a nil node, it means, the new node should be created there
  # Duplicate values are not inserted in the tree
  def insert(value)
    puts "Inserting :" + value.to_s
    current_node = @root
    while nil != current_node
      if (value < current_node.value) && (current_node.left == nil)
        current_node.left = TreeNode.new(value, nil, nil)
      elsif (value > current_node.value) && (current_node.right == nil)
        current_node.right = TreeNode.new(value, nil, nil)
      elsif (value < current_node.value)
        current_node = current_node.left
      elsif (value > current_node.value)
        current_node = current_node.right
      else
        return
      end
    end
  end
end

bst = BinarySearchTree.new(10)
bst.insert(11)
bst.insert(9)
bst.insert(5)
bst.insert(7)
bst.insert(18)
bst.insert(17)
# Demonstrating Different Kinds of Traversals
puts "In-Order Traversal:"
bst.inOrderTraversal
puts "Pre-Order Traversal:"
bst.preOrderTraversal
puts "Post-Order Traversal:"
bst.postOrderTraversal

=begin

   Output :
     Initializing with: 10
   Inserting :11
   Inserting :9
   Inserting :5
   Inserting :7
   Inserting :18
   Inserting :17
   In-Order Traversal:
     5
   7
   9
   10
   11
   17
   18
   Pre-Order Traversal:
     7
   5
   9
   17
   18
   11
   10
   Post-Order Traversal:
     10
   9
   5
   7
   11
   18
   17

   =end

Ref: http://www.thelearningpoint.net/computer-science/basic-data-structures-in-ruby---binary-search-tre

0

@pranshantb1984 - The ref you gave is good one but I think there is a small change in code. Need to update PreOrder and PostOrder code as given below

# Post-Order Traversal
def postOrderTraversal(node= @root)
    return if (node == nil)
    postOrderTraversal(node.left)
    postOrderTraversal(node.right)
    puts node.value.to_s
end 

# Pre-Order Traversal
def preOrderTraversal(node = @root)
    return if (node == nil)
    puts node.value.to_s
    preOrderTraversal(node.left)
    preOrderTraversal(node.right)
end

Pre Order Traversal

10 -> 9 -> 5 -> 7 -> 11 -> 18 -> 17

Post Order Traversal

7 -> 5 -> 9 -> 17 -> 18 -> 11 -> 10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.