Add setValue and nodeCopy methods to binary tree node.

trekhleb · trekhleb · commit 233458363530 · 2018-06-22T08:22:12.000+03:00
diff --git a/src/data-structures/tree/BinaryTreeNode.js b/src/data-structures/tree/BinaryTreeNode.js
@@ -85,6 +85,16 @@ export default class BinaryTreeNode {
     return this.parent.parent.left;
   }
 
+  /**
+   * @param {*} value
+   * @return {BinaryTreeNode}
+   */
+  setValue(value) {
+    this.value = value;
+
+    return this;
+  }
+
   /**
    * @param {BinaryTreeNode} node
    * @return {BinaryTreeNode}
@@ -168,6 +178,16 @@ export default class BinaryTreeNode {
     return false;
   }
 
+  /**
+   * @param {BinaryTreeNode} sourceNode
+   * @param {BinaryTreeNode} targetNode
+   */
+  static copyNode(sourceNode, targetNode) {
+    targetNode.setValue(sourceNode.value);
+    targetNode.setLeft(sourceNode.left);
+    targetNode.setRight(sourceNode.right);
+  }
+
   /**
    * @return {*[]}
    */
diff --git a/src/data-structures/tree/__test__/BinaryTreeNode.test.js b/src/data-structures/tree/__test__/BinaryTreeNode.test.js
@@ -257,4 +257,41 @@ describe('BinaryTreeNode', () => {
     expect(child.uncle).toBeDefined();
     expect(child.uncle).toEqual(uncle);
   });
+
+  it('should be possible to set node values', () => {
+    const node = new BinaryTreeNode('initial_value');
+
+    expect(node.value).toBe('initial_value');
+
+    node.setValue('new_value');
+
+    expect(node.value).toBe('new_value');
+  });
+
+  it('should be possible to copy node', () => {
+    const root = new BinaryTreeNode('root');
+    const left = new BinaryTreeNode('left');
+    const right = new BinaryTreeNode('right');
+
+    root
+      .setLeft(left)
+      .setRight(right);
+
+    expect(root.toString()).toBe('left,root,right');
+
+    const newRoot = new BinaryTreeNode('new_root');
+    const newLeft = new BinaryTreeNode('new_left');
+    const newRight = new BinaryTreeNode('new_right');
+
+    newRoot
+      .setLeft(newLeft)
+      .setRight(newRight);
+
+    expect(newRoot.toString()).toBe('new_left,new_root,new_right');
+
+    BinaryTreeNode.copyNode(root, newRoot);
+
+    expect(root.toString()).toBe('left,root,right');
+    expect(newRoot.toString()).toBe('left,root,right');
+  });
 });
diff --git a/src/data-structures/tree/binary-search-tree/BinarySearchTreeNode.js b/src/data-structures/tree/binary-search-tree/BinarySearchTreeNode.js
@@ -99,7 +99,7 @@ export default class BinarySearchTreeNode extends BinaryTreeNode {
         parent.removeChild(nodeToRemove);
       } else {
         // Node has no parent. Just erase current node value.
-        nodeToRemove.value = null;
+        nodeToRemove.setValue(undefined);
       }
     } else if (nodeToRemove.left && nodeToRemove.right) {
       // Node has two children.
@@ -108,20 +108,24 @@ export default class BinarySearchTreeNode extends BinaryTreeNode {
       const nextBiggerNode = nodeToRemove.right.findMin();
       if (!this.nodeComparator.equal(nextBiggerNode, nodeToRemove.right)) {
         this.remove(nextBiggerNode.value);
-        nodeToRemove.value = nextBiggerNode.value;
+        nodeToRemove.setValue(nextBiggerNode.value);
       } else {
         // In case if next right value is the next bigger one and it doesn't have left child
         // then just replace node that is going to be deleted with the right node.
-        nodeToRemove.value = nodeToRemove.right.value;
-        nodeToRemove.right = nodeToRemove.right.right;
+        nodeToRemove.setValue(nodeToRemove.right.value);
+        nodeToRemove.setRight(nodeToRemove.right.right);
       }
     } else {
       // Node has only one child.
       // Make this child to be a direct child of current node's parent.
-      const child = nodeToRemove.left || nodeToRemove.right;
-      nodeToRemove.value = child.value;
-      nodeToRemove.setLeft(child.left);
-      nodeToRemove.setRight(child.right);
+      /** @var BinarySearchTreeNode */
+      const childNode = nodeToRemove.left || nodeToRemove.right;
+
+      if (parent) {
+        parent.replaceChild(nodeToRemove, childNode);
+      } else {
+        BinaryTreeNode.copyNode(childNode, nodeToRemove);
+      }
     }
 
     return true;
