Ruby Binary Search Tree insert method stack level too deep

Question

I am trying to write a recursive insert method for a binary search tree but keep getting stack level too deep What is going on that it keeps giving me the error?

my node class

class Node
  attr_accessor :value, :left, :right

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

binary search tree class

class Bst
  attr_accessor :root, :size

  def initialize
    @root = nil
    @size = 0
  end

  def insert(value, root=nil)
    if @root == nil
      @root = Node.new(value)
    end
    if value < @root.value
      if @root.left == nil
        @root.left = Node.new(value)
      else
        return insert(value, @root.left)
      end
      return root
    end
    if value > @root.value
      if @root.right == nil
        @root.right = Node.new(value)
      else
        return insert(value, @root.right)
      end
    end
    return root
  end

It happens once I try to add 4 to the tree

tree = Bst.new
tree.insert(10)
tree.insert(6)
tree.insert(19)
tree.insert(4)

Answer 1

When you recurse and provide new root, you are still comparing the value with @root.value.

Since 4 is still less than 10, you recurse, and pass @root.left as root. However, root is never used; you are again comparing @root.value, and recursing with @root.left, and those never change; thus, you have infinite recursion (or at least infinite till you blow the stack).

You want to be comparing to root.value, and recursing with root.left instead.

Having @root and root be different things is confusing, and leads to logic errors. Better variable naming would likely have prevented this error.

EDIT:

class Node
  attr_accessor :value, :left, :right

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

class Bst
  attr_accessor :root, :size

  def initialize
    @root = nil
    @size = 0
  end

  def insert(value, node=nil)
    unless @root
      @root = Node.new(value)
      return
    end

    node ||= @root

    if value < node.value
      if node.left
        return insert(value, node.left)
      else
        node.left = Node.new(value)
      end
    elsif value > node.value
      if node.right
        return insert(value, node.right)
      else
        node.right = Node.new(value)
      end
    end
    @size += 1
    return node
  end
end

tree = Bst.new
tree.insert(10)
tree.insert(6)
tree.insert(19)
tree.insert(4)

p tree