is valid bst

1 files changed, 54 insertions, 0 deletions

diff --git a/2022/04/05/main.rb b/2022/04/05/main.rb
new file mode 100644
index 0000000..807d7d4
--- /dev/null
+++ b/2022/04/05/main.rb
@@ -0,0 +1,54 @@
+# Given a tree, determine if it is a valid binary search tree.
+
+def assert_equal(x, y)
+  raise "Expected: #{x}, Got: #{y}" unless x == y
+end
+
+class Node
+  attr_accessor :right, :left
+  attr_reader :value
+
+  def initialize(value)
+    @value = value
+  end
+end
+
+class Solution
+  def self.in_range?(node, low, high)
+    return true if node.nil?
+    return false if node.value < low
+    return false if node.value > high
+
+    return in_range?(node.left, low, node.value) &&
+      in_range?(node.right, node.value, high)
+  end
+
+  def self.is_valid?(tree)
+    in_range?(tree, -100, 100)
+  end
+end
+
+=begin
+    5
+   / \
+  4   7
+=end
+tree = Node.new(5)
+tree.left = Node.new(4)
+tree.right = Node.new(7)
+
+assert_equal true, Solution.is_valid?(tree)
+
+=begin
+    5
+   / \
+  4   7
+     /
+    2
+=end
+tree = Node.new(5)
+tree.left = Node.new(4)
+tree.right = Node.new(7)
+tree.right.left = Node.new(2)
+
+assert_equal false, Solution.is_valid?(tree)