Is this use of Ruby wrong for a binary search tree?

Question

I tried to write a quick implementation for a binary search tree in Ruby, which is a data structure I commonly write when learning a new programming language.

I get stack too deep errors when I run it on my computer. I wonder if it is an issue with my code or perhaps how I'm running it?

class Node
  attr_accessor :data, :left, :right
  def initialize(d)
    @data = d
    @left = Node.new(nil)
    @right = Node.new(nil)
  end
end

class BST
  attr_accessor :root
  def initialize
    @root = nil
  end

  def add_recursive(r, d)
    if r == nil
      r = Node.new(d)
    else
      add_recursive(r.right, d) if d > r.data
      add_recursive(r.left, d) if d < r.data  
    end
  end

  def add(darg)
    add_recursive(@root, darg)
  end

  def pr(r)
    if (r.left != nil)
      pr(r.left)
    end
    print "#{r.data}"
    if (r.right != nil)
      pr(r.right)
    end
  end
end

bb = BST.new
bb.add(100)
bb.add(0)
bb.add(-100)
bb.pr(bb.root)``

I was wondering what am I doing wrong in this implementation because I did indeed run a few simple tests and my use in accessing the data variable was giving me problems. Thanks for any help

I'd probably use @left = nil and @right = nil for a new node rather than have left and right point to valid nodes that just have nil data. — lurker
– lurker, Commented Oct 19, 2013 at 2:35

Peter Alfvin · Accepted Answer · 2013-10-19 03:44:19Z

1

You've got more than one problem here, but your infinite recursion is occurring with your first Node.new(nil) call in Node#initialize. Another problem is that you never update @root in BST after you initialize it to nil. In add_recursive your assignment to r has no effect on @root.

answered Oct 19, 2013 at 3:44

Peter Alfvin

29.6k9 gold badges72 silver badges114 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Is this use of Ruby wrong for a binary search tree?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related