binary-search-tree - npm Package Compare versions

Comparing version 0.1.0 to 0.1.1

lib/bst.js

@@ -362,13 +362,25 @@ /**
     replaceWith = this.left.getMaxKeyDescendant();
+
     this.key = replaceWith.key;
     this.data = replaceWith.data;
-    replaceWith.parent.right = replaceWith.left;
-    if (replaceWith.left) { replaceWith.left.parent = replaceWith.parent; }
+
+    if (this === replaceWith.parent) {   // Special case
+      this.left = replaceWith.left;
+    } else {
+      replaceWith.parent.right = replaceWith.left;
+      if (replaceWith.left) { replaceWith.left.parent = replaceWith.parent; }
+    }
   } else {
     // Use the in-order successor
     replaceWith = this.right.getMinKeyDescendant();
+
     this.key = replaceWith.key;
     this.data = replaceWith.data;
-    replaceWith.parent.left = replaceWith.right;
-    if (replaceWith.right) { replaceWith.right.parent = replaceWith.parent; }
+
+    if (this === replaceWith.parent) {   // Special case
+      this.right = replaceWith.right;
+    } else {
+      replaceWith.parent.left = replaceWith.right;
+      if (replaceWith.right) { replaceWith.right.parent = replaceWith.parent; }
+    }
   }
@@ -375,0 +387,0 @@ };

package.json

 {
   "name": "binary-search-tree",
-  "version": "0.1.0",
+  "version": "0.1.1",
   "author": {
@@ -5,0 +5,0 @@ "name": "Louis Chatriot",

test/bst.test.js

@@ -706,4 +706,18 @@ var should = require('chai').should()
 
+    it('Can remove the root from a tree with height 2 when the root has two children (special case)', function () {
+      var bst = new BinarySearchTree();
+
+      bst.insert(10, 'maybe');
+      bst.insert(5, 'no');
+      bst.insert(15, 'yes');
+      bst.getNumberOfKeys().should.equal(3);
+
+      bst.delete(10);
+      bst.getNumberOfKeys().should.equal(2);
+      assert.deepEqual(bst.search(5), ['no']);
+      assert.deepEqual(bst.search(15), ['yes']);
+    });
+
   });   // ==== End of 'Deletion' ==== //
 
 });

No alert changes

Improved metrics

Total package byte prevSize

38848

increased by1.83%

Lines of code

945

increased by2.05%

No dependency changes