k-ary-tree-generator.rb

class Tree
  attr_accessor :payload, :children

  def initialize(payload, children)
    @payload = payload
    @children = children
  end

  def self.build_k_ary_tree(array, k) #where k = number of children per node
    raise Exception, 'A node cannot have a negative number of children' if k < 0
    first = array.first
    rest = array.last(array.length-1) #or array[1..array.length-1], rest of the array
    trunk = Tree.new(first, Array.new(k, nil)) 
    # the root, where payload is the first item of the array and 
    #children an array of k nil elements
    
    rest.each do |i| #looping through the rest of the array
      queue = [] #implementing a queue with an empty array so we can perform a 
                 #breadth-first walk through our tree to place the nodes
      queue.push(trunk)
      node = Tree.new(i, Array.new(k, nil)) #new node to be placed in the tree,
                                   #with payload i and children an array of k nil elements
      while queue.length != 0 do 
        current = queue.shift
          if current.children.include?(nil)
            #attribute the node to the next children which is nil:
            current.children[current.children.index(nil)] = node
            queue.clear #if the new node is sucessfully placed (line above),
            #clear the queue to exit the while loop and jump to the next i value
          else
              #if no children is nil, then they should all go in the queue so the while 
              #loop goes on until the next nil element is found and our node is attributed: 
              current.children.each do |child|
                queue.push(child) 
              end
          end   
      end
    end
    return trunk
  end
end