CODEWITHSUNDEEP
rubybinary-search-tree
Arthur Collé
Arthur Collé

Reputation: 2607

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

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

Upvotes: 0

Views: 650

Answers (1)

Peter Alfvin
Peter Alfvin

Reputation: 29399

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.

Upvotes: 1

Related Questions