What's wrong in this recursive tree building algorithm that's currently leading to it overflowing?

Question

I'm learning about binary trees and am trying to write a recursive method that builds a balanced binary tree when given a sorted array. I'm stuck with an overflow condition and don't exactly see what I'm doing wrong and how to fix. Some guidance would be very helpful. The method in question is #build_balanced_tree(array), all relevant code to produce a reproducible example is below:

class Node
  attr_accessor :value, :left, :right
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

class Tree
  attr_reader :array
  attr_accessor :root

  def initialize
    @array = nil
    @root = nil
  end

  def build_balanced_tree(array)
    return if array.empty?
    array_mid_index = (array.length - 1) / 2
    self.root = Node.new(array[array_mid_index])
    self.root.left = build_balanced_tree(array[0..(array_mid_index - 1)])
    self.root.right = build_balanced_tree(array[(array_mid_index + 1)..(array.length - 1)])
    return root
  end
end

array = [1, 4, 7, 13, 65, 97]
tree = Tree.new
p tree.build_balanced_tree(array)

This error message; :in 'new': stack level too deep (SystemStackError) is thrown when the code hits the self.root.left = ... line and passes the left half of the array back into itself.

I suspect that part of the issue may be that my recursive method is setting self.root and that because @root is explicitly named it recursively keeps overwriting itself, but I cannot quite envision how to anonymise the Node creation and value setting whilst making sure @root is set on the first iteration. There may be multiple other problems with this code also, which I'd appreciate any help with. Thank you.

Answer 1

The reason for the infinite recursion is that array[0..(array_mid_index - 1)] can become array[0..-1], which means the whole array, while you really wanted to get an empty array when array_mid_index is 0.

There are several ways to solve that; one is to use slice, which takes a length as second argument, and so that could be array_mid_index. Then there is no such misinterpretation possible.

You are also right that there is an issue with assigning to self.root. You only want that assignment to happen once, which means you should not perform that assignment in the function that will be called recursively, but in a separate function.

I would propose to create a static method for this purpose, as it feels unnatural that the caller would have to create a new Tree instance before they can actually call this function. The static method could create that new instance itself and return it after it has been populated.

The recursive function could become a static method on the Node class, since it does not need any knowledge of the Tree class.

NB: you don't need that @array attribute on the Tree class. The array is just an argument that is used temporarily to build a tree and then has no role to play in the state of the tree.

Here is how that would look:

class Node
  attr_accessor :value, :left, :right
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end

  def self.build_balanced_tree(array)
    return if array.empty?
    array_mid_index = (array.length - 1) / 2
    node = Node.new(array[array_mid_index])
    node.left = build_balanced_tree(array.slice(0, array_mid_index))
    node.right = build_balanced_tree(array[(array_mid_index + 1)...])
    return node
  end
end

class Tree
  attr_accessor :root

  def initialize
    @root = nil
  end

  def self.build_balanced_tree(array)
    tree = Tree.new
    tree.root = Node.build_balanced_tree(array)
    return tree
  end
end

array = [1, 4, 7, 13, 65, 97]
p Tree.build_balanced_tree(array)