tree_node.rb

#!/usr/bin/ruby

class Node
  attr_accessor :name, :parent

  def initialize(name, parent=nil)
    @name = name;
    @parent = parent;
  end

  def to_s
    ps = parent.nil? ? 'nil' : "(#{parent.name})"
    "[#{name}]->#{ps}"
  end

  def depth(c=1)
    if parent.nil?
      return c
    else
      parent.depth(c + 1)
    end
  end

  def ancestor(steps=0)
    return nil if parent.nil?
    p = self
    steps.times { p = p.parent }
    p
  end

  def common_ancestor(n)
    d = [depth, n.depth]
    if d[0] == d[1]
      return parent
    elsif d[0] > d[1]
      n.ancestor(d[0] - d[1])
    elsif d[0] < d[1]
      ancestor(d[1] - d[0])
    end
  end
end


# create a tree
p = nil
%w{c d e f g h i j}.each do |s|
  n = Node.new(s,p)
  p = n
end
m = Node.new("m",p.ancestor(3))
b = Node.new('b',m) # [m]<-[b]       [a]
a = Node.new('a',p) #  |              |
# [c]<-[d]<-[e]<-[f]<-[g]<-[h]<-[i]<-[j]

puts a
puts b
puts m
puts a.common_ancestor(b)
puts a.common_ancestor(Node.new('x'))
puts Node.new('x')

__END__

[a]->(j)
[b]->(m)
[m]->(g)
[g]->(f)
nil
[x]->nil