O(N**2)

is_tree_sorted.rb

require 'minitest/autorun'

Tree = Struct.new(:value, :left, :right)


class TestTree < Minitest::Test
  def test_is_tree_sorted_true
    seven = Tree.new(7)
    three = Tree.new(3)
    five = Tree.new(5, three, seven)

    assert_equal true, is_tree_sorted(five)
  end

  def test_is_tree_sorted_false
    seven = Tree.new(7)
    three = Tree.new(3, nil, seven)
    five = Tree.new(5, three)

    assert_equal false, is_tree_sorted(five)
  end
end


def is_tree_sorted(root)
  left = root.left
  right = root.right

  unless right.nil?
    if lowest_value(right) < root.value
      return false
    end
    if is_tree_sorted(right) == false
      return false
    end
  end

  unless left.nil?
    if highest_value(left) > root.value
      return false
    end
    if is_tree_sorted(left) == false
      return false
    end
  end

  true
end

def highest_value(root)
  find_value_with_block(root) do |max, child|
    max > highest_value(child) ? max : highest_value(child)
  end
end

def lowest_value(root)
  find_value_with_block(root) do |min, child|
    min < lowest_value(child) ? min : lowest_value(child)
  end
end

def find_value_with_block(root, &block)
  return root.value if root.left.nil? && root.right.nil?
  left = root.left
  right = root.right

    [left, right].compact.inject(root.value) do |value, child|
      yield [value, child]
    end
end