largest bst. not optimal but sort of works

2 files changed, 57 insertions, 2 deletions

diff --git a/2020/09/29/README.md b/2020/09/29/README.md
index 354bc3c..a18c9eb 100644
--- a/2020/09/29/README.md
+++ b/2020/09/29/README.md
@@ -1,5 +1,6 @@
-You are given the root of a binary tree. Find and return the largest
-subtree of that tree, which is a valid binary search tree.
+You are given the root of a binary tree.
+Find and return the largest subtree of that tree,
+which is a valid binary search tree.
 
 Here's a starting point:
 
diff --git a/2020/09/29/main.rb b/2020/09/29/main.rb
new file mode 100644
index 0000000..633e354
--- /dev/null
+++ b/2020/09/29/main.rb
@@ -0,0 +1,54 @@
+
+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!"