A tree for creating parenthesis permutation

parens_permute.rb

require 'graphviz'

class LeveledBinaryTree
  Node = Struct.new(:weight, :str, :left, :right)

  attr_accessor :levels, :root

  def initialize(clear_last_level = true)
    @root = Node.new(1, '(')
    @levels = {0 => [@root]}
    @clear_last_level = clear_last_level
  end

  def construct(n)
    @max_level = 2*n - 1
    1.upto(@max_level - 1).each do |current_level|
      @levels[current_level]  = []
      @levels[current_level - 1].each do |node|
        @levels[current_level] << node.left = Node.new(node.weight + 1, node.str + '(') if node_possible?(current_level, node.weight + 1)
        @levels[current_level] << node.right = Node.new(node.weight - 1, node.str + ')') if node_possible?(current_level, node.weight - 1)
      end
      @levels[current_level - 1] = nil if @clear_last_level
    end
  end

  def last_level
    @levels[@max_level - 1]
  end

  def draw
    GraphViz::new( :G, :type => :'strict digraph', :ordering =>"out" ) do |g|
      0.upto(@max_level - 1).each do |current_level|
        @levels[current_level].each do |node|
          cur_node = g.find_node(node.object_id.to_s) || g.add_nodes(node.object_id.to_s, :label => "#{node.str} -> #{node.weight}")
          [[node.left, "left"], [node.right, "right"]].each do |child, label|
            next unless child
            child_node = g.add_nodes(child.object_id.to_s, :label => "#{child.str} -> #{child.weight}")
            g.add_edges(cur_node, child_node, :label => label, :sametail => '1')
          end
        end
      end
    end.output( :png => 'wac8.png' )
  end

  private
  def node_possible?(current_level, weight)
    weight >= 0 && weight <= (@max_level - current_level)
  end
end


tree = LeveledBinaryTree.new(false)
tree.construct(3)
tree.draw
tree.last_level.each{|x| puts x.str + ')'}