def assert_equals(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
  def self.run(tree, level = 0)
    return unless tree
    return tree if bst?(tree, -100, 100)

    left = run(tree.left, level + 1)
    right = run(tree.right, level + 1)

    if left && right
      left_size = size(left)
      right_size = size(right);
      left_size > right_size ? tree.left : tree.right
    else
      tree.left || tree.right
    end
  end

  def self.size(tree, s = 0)
    return s if tree.nil?

    size(tree.left, s) + size(tree.right, s) + 1
  end

  def self.bst?(tree, min, max)
    return true if tree.nil?
    return if tree.left && tree.left.value > min
    return if tree.right && tree.right.value < max

    bst?(tree.left, min, tree.value) && bst?(tree.right, tree.value, max)
  end
end

node = Node.new(5)
node.left = Node.new(6)
node.right = Node.new(7)
node.left.left = Node.new(2)
node.right.left = Node.new(4)
node.right.right = Node.new(9)

assert_equals(Solution.run(node)&.value, node.right&.value)
puts "YAY!"