1def assert_equal(x, y)
 2  raise [x, y].inspect unless x == y
 3end
 4
 5class Node
 6  attr_accessor :left, :right, :value
 7
 8  def initialize(value)
 9    @value = value
10  end
11end
12
13class Solution
14  # time: O(logn)
15  # space: O(n)
16  def self.run(root, target, floor = nil, ceiling = nil)
17    return [floor, ceiling] if root == target
18
19    if target > root.value
20      if root.right
21        run(root.right, target, root.value, ceiling)
22      else
23        [root.value, ceiling]
24      end
25    else
26      if root.left
27        run(root.left, target, floor, root.value)
28      else
29        [floor, root.value]
30      end
31    end
32  end
33end
34
35=begin
36       8
37     /    \
38    4     12
39   / \   /  \
40  2   6 10  14
41
42=end
43
44root = Node.new(8)
45root.left = Node.new(4)
46root.right = Node.new(12)
47
48root.left.left = Node.new(2)
49root.left.right = Node.new(6)
50
51root.right.left = Node.new(10)
52root.right.right = Node.new(14)
53
54assert_equal([nil, 2], Solution.run(root, 1))
55assert_equal([2, 4], Solution.run(root, 3))
56assert_equal([4, 6], Solution.run(root, 5))
57assert_equal([10, 12], Solution.run(root, 11))
58assert_equal([12, 14], Solution.run(root, 13))
59assert_equal([14, nil], Solution.run(root, 15))
60puts "Yay!"