delete from bst without recursive delete

4 files changed, 34 insertions, 13 deletions

diff --git a/Gemfile b/Gemfile
index d509419..04bed46 100644
--- a/Gemfile
+++ b/Gemfile
@@ -4,3 +4,4 @@ source "https://rubygems.org"
 gem 'rspec'
 gem 'byebug'
 gem 'ruby-prof'
+gem 'diffy'
diff --git a/Gemfile.lock b/Gemfile.lock
index 0bfd647..ac6d1be 100644
--- a/Gemfile.lock
+++ b/Gemfile.lock
@@ -3,6 +3,7 @@ GEM
   specs:
     byebug (9.0.6)
     diff-lcs (1.3)
+    diffy (3.2.0)
     rspec (3.6.0)
       rspec-core (~> 3.6.0)
       rspec-expectations (~> 3.6.0)
@@ -23,6 +24,7 @@ PLATFORMS
 
 DEPENDENCIES
   byebug
+  diffy
   rspec
   ruby-prof
 
diff --git a/spec/binary_trees/delete_from_bst_spec.rb b/spec/binary_trees/delete_from_bst_spec.rb
index 3bc85d0..7526cde 100644
--- a/spec/binary_trees/delete_from_bst_spec.rb
+++ b/spec/binary_trees/delete_from_bst_spec.rb
@@ -191,19 +191,28 @@ they want you to take the largest node's left subtree and make it the child of t
       elsif tree.right.nil?
         return tree.left
       else
-        max = tree.left
-        max = max.right while max.right
-        min = tree.right
-        min = min.left while min.left
-
-        puts [max&.value, min&.value].inspect
+        max, parent = tree.left, tree
+        while max.right
+          parent = max
+          max = max.right
+        end
 
         tree.value = max.value
-        tree.left = remove(tree.left, tree.value)
-
+        if parent == tree
+          tree.left = tree.left.left
+        else
+          parent&.right = max.left
+        end
+
+        #max = tree.left
+        #max = max.right while max.right
+        #tree.value = max.value
+        #tree.left = remove(tree.left, tree.value)
+
+        #min = tree.right
+        #min = min.left while min.left
         #tree.value = min.value
         #tree.right = remove(tree.right, tree.value)
-
       end
     end
     tree
@@ -211,7 +220,11 @@ they want you to take the largest node's left subtree and make it the child of t
 
   def delete_from_bst(tree, queries)
     return nil if tree.nil?
-    queries.each { |query| tree = remove(tree, query) }
+    queries.each do |target|
+      #puts [target].inspect
+      #tree&.print
+      tree = remove(tree, target)
+    end
     tree
   end
 
@@ -248,7 +261,7 @@ they want you to take the largest node's left subtree and make it the child of t
     x = SPEC9
     result = delete_from_bst(Tree.build_from(x[:t]), x[:queries])
     expected = x[:x] ? Tree.build_from(x[:x]).to_s : nil
-    expect(result ? result.to_s : result).to eql(expected)
+    expect(result.to_s).to eql(expected)
   end
 
   it do
@@ -256,6 +269,6 @@ they want you to take the largest node's left subtree and make it the child of t
     x = SPEC10
     result = delete_from_bst(Tree.build_from(x[:t]), x[:queries])
     expected = x[:x] ? Tree.build_from(x[:x]).to_s : nil
-    expect(result ? result.to_s : result).to eql(expected)
+    expect(result.to_s).to eql(expected)
   end
 end
diff --git a/spec/spec_helper.rb b/spec/spec_helper.rb
index 026ea46..f07ff8a 100644
--- a/spec/spec_helper.rb
+++ b/spec/spec_helper.rb
@@ -14,8 +14,9 @@
 #
 # See http://rubydoc.info/gems/rspec-core/RSpec/Core/Configuration
 require 'byebug'
-require 'ruby-prof'
+require 'diffy'
 require 'pp'
+require 'ruby-prof'
 require_relative '../lib/tree'
 
 RSpec.configure do |config|
@@ -112,4 +113,8 @@ RSpec.configure do |config|
     printer.print(STDOUT, {})
     result
   end
+
+  def print_diff(x, y)
+    puts Diffy::Diff.new(x, y).to_s(:color)
+  end
 end