Lowest Common Ancestor

B木の共通の祖先で最短のものを表示。

いきなり難易度が上がった感じ。これ苦手だわ。
とりあえずB木をどう表現するかが肝っぽい。

設問

Write a program to determine the lowest common ancestor of two nodes in a binary search tree. You may hardcode the following binary search tree in your program:

    30
    |
  ____
  |   |
  8   52
  |
____
|   |
3  20
    |
   ____
  |   |
  10 29

Input sample:

The first argument will be a text file containing 2 values that represent two nodes within the tree, one per line. e.g.

8 52
3 29

Output sample:

Print to stdout, the least common ancestor, one per line.
e.g.

30
8

やってみた

#!/usr/bin/env ruby
class Node
  attr_accessor :value, :left, :right

  def initialize(value=nil)
    @value = value
    @left, @right = nil, nil
  end
  
  def ancestor(n)
    return value if (left and n == left.value) or (right and n == right.value)

    left.ancestor(n).instance_eval{ |v| return v if v } if left
    right.ancestor(n).instance_eval{ |v| return v if v } if right
  end

  def ancestors(n, arr=[])
    anc = ancestor(n)
    return arr unless anc

    arr << anc
    ancestors(anc, arr)
  end
end

tree = Node.new(30)
tree.left = Node.new(8)
tree.left.left = Node.new(3)
tree.left.right = Node.new(20)
tree.left.right.left = Node.new(10)
tree.left.right.right = Node.new(29)
tree.right = Node.new(52)

ARGF.lines do |line|
  a, b = line.split(/\s/).map(&:to_i)
  puts (tree.ancestors(a) & tree.ancestors(b)).first
end

どうもtreeデータの作成が汚いなぁ。
あと、ancestor取得のところもleft/rightで一緒なのでなんとかならんかな。