random_tree_generator.rb

  def self.build_random_tree(array, k)
    raise Exception, 'A node cannot have a negative number of children' if k < 0
    first = array.delete_at(rand(array.length)) #choose randomly an item and remove it
    rest = array.shuffle! #shuffle the rest of the array
    trunk = Tree.new(first, Array.new(rand(k+1), nil))  #trunk is created with an array 
    #made of a random number nil elements that is greater or equal to 0 and less than k+1 
    #(i.e. less or equal to k). In other words, with a number of nodes between zero and k
    
    rest.each do |i|
      queue = [trunk] 
      node = Tree.new(i, Array.new(rand(k+1), nil)) 
      #the new node, with payload i and as children an array of between zero and k nil 
      #elements (futur potential nodes), randomly generated for each node
      while !queue.empty? do
        current = queue.shift
          if current.children.include?(nil)
            current.children[current.children.index(nil)] = node
            queue.clear
          else
              current.children.each do |child|
                queue.push(child) 
              end
          end   
      end
    end
    return trunk
  end