def assert_equal(x, y)
  raise [x, y].inspect unless x == y
end

class Node
  attr_accessor :left, :right, :value

  def initialize(value)
    @value = value
  end
end

class Solution
  # time: O(logn)
  # space: O(n)
  def self.run(root, target, floor = nil, ceiling = nil)
    return [floor, ceiling] if root == target

    if target > root.value
      if root.right
        run(root.right, target, root.value, ceiling)
      else
        [root.value, ceiling]
      end
    else
      if root.left
        run(root.left, target, floor, root.value)
      else
        [floor, root.value]
      end
    end
  end
end

=begin
       8
     /    \
    4     12
   / \   /  \
  2   6 10  14

=end

root = Node.new(8)
root.left = Node.new(4)
root.right = Node.new(12)

root.left.left = Node.new(2)
root.left.right = Node.new(6)

root.right.left = Node.new(10)
root.right.right = Node.new(14)

assert_equal([nil, 2], Solution.run(root, 1))
assert_equal([2, 4], Solution.run(root, 3))
assert_equal([4, 6], Solution.run(root, 5))
assert_equal([10, 12], Solution.run(root, 11))
assert_equal([12, 14], Solution.run(root, 13))
assert_equal([14, nil], Solution.run(root, 15))
puts "Yay!"