first cut.

1 files changed, 54 insertions, 2 deletions

diff --git a/spec/binary_trees/delete_from_bst_spec.rb b/spec/binary_trees/delete_from_bst_spec.rb
index 8379cdf..37f079e 100644
--- a/spec/binary_trees/delete_from_bst_spec.rb
+++ b/spec/binary_trees/delete_from_bst_spec.rb
@@ -35,7 +35,8 @@ And removing 6 after that creates the following tree:
   2   8
  /   /
 1   7
-You're given a binary search tree t and an array of numbers queries. Your task is to remove queries[0], queries[1], etc., from t, step by step, following the algorithm above. Return the resulting BST.
+You're given a binary search tree t and an array of numbers queries. Your task is to remove queries[0], queries[1],
+etc., from t, step by step, following the algorithm above. Return the resulting BST.
 
 Example
 
@@ -118,7 +119,55 @@ The tree after removing all the numbers in queries, following the algorithm abov
 DOC
 
 describe "#delete_from_bst" do
+<<-DOC
+  If there is no x in t, nothing happens;
+  Otherwise, let t' be a subtree of t such that t'.value = x.
+  If t' has a left subtree, remove the rightmost node from it and put it at the root of t';
+  Otherwise, remove the root of t' and its right subtree becomes the new t's root.
+DOC
+
+  def rightmost(tree)
+    return nil if tree.nil?
+
+    tree.right.nil? ? tree : rightmost(tree.right)
+  end
+
+  def parent_of(tree, target)
+    return nil if tree.nil?
+
+    return tree if tree.right && target == tree.right.value
+    parent_of(tree.right)
+  end
+
+  def remove(tree, target)
+    return nil if tree.nil?
+
+    if target == tree.value
+      if tree.left
+        new_root = rightmost(tree.left)
+        old_parent = parent_of(tree.left, new_root.value)
+        old_parent&.right = nil
+        new_root.left = tree.left
+        new_root.right = tree.right
+        tree = new_root
+      else
+        tree.right
+      end
+    else
+      tree.left = remove(tree.left, target)
+      tree.right = remove(tree.right, target)
+    end
+    tree
+  end
+
   def delete_from_bst(tree, queries)
+    return tree if tree.nil?
+    tree.print
+
+    queries.each do |query|
+      tree = remove(tree, query)
+    end
+
     tree
   end
 
@@ -132,7 +181,10 @@ describe "#delete_from_bst" do
     { t: { "value": 5, "left": { "value": 3, "left": { "value": 1, "left": null, "right": null }, "right": { "value": 4, "left": null, "right": null } }, "right": { "value": 7, "left": null, "right": null } }, queries: [1, 7, 4, 6], x: { "value": 5, "left": { "value": 3, "left": null, "right": null }, "right": null } },
   ].each do |x|
     it do
-      expect(delete_from_bst(Tree.build_from(x[:t]), x[:queries]).to_h).to eql(x[:x])
+      result = delete_from_bst(Tree.build_from(x[:t]), x[:queries])
+      puts x[:queries].inspect
+      result.print
+      expect(result.to_h).to eql(x[:x])
     end
   end
 end