1
 2def assert_equals(x, y)
 3  raise [x, y].inspect unless x == y
 4end
 5
 6class Node
 7  attr_accessor :left, :right, :value
 8
 9  def initialize(value)
10    @value = value
11  end
12end
13
14class Solution
15  def self.run(tree, level = 0)
16    return unless tree
17    return tree if bst?(tree, -100, 100)
18
19    left = run(tree.left, level + 1)
20    right = run(tree.right, level + 1)
21
22    if left && right
23      left_size = size(left)
24      right_size = size(right);
25      left_size > right_size ? tree.left : tree.right
26    else
27      tree.left || tree.right
28    end
29  end
30
31  def self.size(tree, s = 0)
32    return s if tree.nil?
33
34    size(tree.left, s) + size(tree.right, s) + 1
35  end
36
37  def self.bst?(tree, min, max)
38    return true if tree.nil?
39    return if tree.left && tree.left.value > min
40    return if tree.right && tree.right.value < max
41
42    bst?(tree.left, min, tree.value) && bst?(tree.right, tree.value, max)
43  end
44end
45
46node = Node.new(5)
47node.left = Node.new(6)
48node.right = Node.new(7)
49node.left.left = Node.new(2)
50node.right.left = Node.new(4)
51node.right.right = Node.new(9)
52
53assert_equals(Solution.run(node)&.value, node.right&.value)
54puts "YAY!"