adjacency list modeling

node.rb

class Node
  attr_accessor :id, :name, :parent, :children

  def initialize(opts = {})
    @id = opts[:id]
    @name = opts[:name]
    @parent = opts[:parent]

    # add children if passed an array or initialize as an empty array
    @children = opts[:children].is_a?(Array) ? opts[:children] : []

  end
end

tree.rb

class Tree
  attr_accessor :nodes

  def initialize
    @nodes = {}
  end

  def node(id)
    @nodes[id]
  end

  # helper for hash-like access
  def [](id)
    node(id)
  end

  def add_node(node)
    raise "#{node.class} != Node" if node.class != Node
    if !node.parent.nil?
      # check if the parent is part of the tree
      existing_parent = self.node(node.parent.id)
      if existing_parent.nil?
        raise "Unable to add node #{node.id} to the tree. It specifies a parent #{node.parent.id} That has not been added to the tree"
      end
      node.parent = existing_parent
      existing_parent.children.push(node.id).uniq
    end
    @nodes[node.id] = node
  end
  def ancestors(node, ancestor_list = [])
    # traverse up the tree to get all parents
    # return the list if the parent of the current node is already in the list
    if node.parent && !ancestor_list.include?(node.parent)
      ancestor_list.push node.parent
      self.ancestors(node.parent, ancestor_list)
    else
      ancestor_list.empty? ? nil : ancestor_list.reverse
    end
  end

  def path(node)
    if node.parent.nil?
      path = node.id.to_s
    else
      path = ancestors(node).push(node).map{ |n| n.id.to_s }.join ':'
    end
  end
end