# 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で一緒なのでなんとかならんかな。