nested_set.rb

#
# i've represented this tree as the array 'tree'.
#   A    B   C    F    G     K
#           / \       / \
#          D   E     H   J
#                   /
#                  I 
#
# According to the nested set rules, the following output should be given:
#   1-A-2  3-B-4  5-C-10     11-F-12    13-G-20     21-K-22
#                /     \                /      \
#             6-D-7  8-E-9           14-H-17  18-J-19
#                                     /
#                                 15-I-16

class Node
  attr_accessor :name
  attr_accessor :children

  attr_accessor :left
  attr_accessor :right

  def initialize name, children = []
    @name     = name
    @children = children
    @left     = nil
    @right    = nil
  end
end

tree = [ Node.new("A"),
         Node.new("B"),
         Node.new("C", [
           Node.new("D"),
           Node.new("E")]),
         Node.new("F"),
         Node.new("G", [
           Node.new("H", [
             Node.new("I") ]),
           Node.new("J")]),
         Node.new("K")]


# The roots are special
def set_root_positions(tree)
  left_counter = 0
  tree.each do |root|
    left_counter = set_positions(root, left_counter)
  end
end

def set_positions(node, parent_left = 0)
  left_counter = parent_left + 1;
  node.left = left_counter

  node.children.each do |child|
    left_counter = set_positions(child, left_counter)
  end

  left_counter += 1
  node.right = left_counter

  return left_counter
end

set_root_positions tree


def display_tree tree
  tree.each do |root|
    display_node root
  end
end

def display_node node, indent = 0
  puts "#{" " * indent}#{node.left}-#{node.name}-#{node.right} ";
  node.children.each do |child|
    display_node(child, indent + 2)
  end
end

display_tree tree

# This outputs:
# 1-A-2
# 3-B-4
# 5-C-10
#   6-D-7
#   8-E-9
# 11-F-12
# 13-G-20
#   14-H-17
#     15-I-16
#   18-J-19
# 21-K-22

# which is equal to what we said that it should be.