1# Given a tree, determine if it is a valid binary search tree.
 2
 3def assert_equal(x, y)
 4  raise "Expected: #{x}, Got: #{y}" unless x == y
 5end
 6
 7class Node
 8  attr_accessor :right, :left
 9  attr_reader :value
10
11  def initialize(value)
12    @value = value
13  end
14end
15
16class Solution
17  def self.in_range?(node, low, high)
18    return true if node.nil?
19    return false if node.value < low
20    return false if node.value > high
21
22    return in_range?(node.left, low, node.value) &&
23      in_range?(node.right, node.value, high)
24  end
25
26  def self.is_valid?(tree)
27    in_range?(tree, -100, 100)
28  end
29end
30
31=begin
32    5
33   / \
34  4   7
35=end
36tree = Node.new(5)
37tree.left = Node.new(4)
38tree.right = Node.new(7)
39
40assert_equal true, Solution.is_valid?(tree)
41
42=begin
43    5
44   / \
45  4   7
46     /
47    2
48=end
49tree = Node.new(5)
50tree.left = Node.new(4)
51tree.right = Node.new(7)
52tree.right.left = Node.new(2)
53
54assert_equal false, Solution.is_valid?(tree)