Add uncle property to binary tree node.

trekhleb · trekhleb · commit 02299b77e6ea · 2018-06-01T05:16:07.000+03:00
diff --git a/src/data-structures/tree/BinaryTreeNode.js b/src/data-structures/tree/BinaryTreeNode.js
@@ -1,4 +1,5 @@
 import Comparator from '../../utils/comparator/Comparator';
+import HashTable from '../hash-table/HashTable';
 
 export default class BinaryTreeNode {
   /**
@@ -11,7 +12,7 @@ export default class BinaryTreeNode {
     this.value = value;
 
     // Any node related meta information may be stored here.
-    this.meta = new Map();
+    this.meta = new HashTable();
 
     // This comparator is used to compare binary tree nodes with each other.
     this.nodeComparator = new Comparator();
@@ -53,6 +54,37 @@ export default class BinaryTreeNode {
     return this.leftHeight - this.rightHeight;
   }
 
+  /**
+   * Get parent's sibling if it exists.
+   * @return {BinaryTreeNode}
+   */
+  get uncle() {
+    // Check if current node has parent.
+    if (!this.parent) {
+      return undefined;
+    }
+
+    // Check if current node has grand-parent.
+    if (!this.parent.parent) {
+      return undefined;
+    }
+
+    // Check if grand-parent has more than two children.
+    if (!this.parent.parent.left || !this.parent.parent.right) {
+      return undefined;
+    }
+
+    // So for now we know that current node has grand-parent and this
+    // grand-parent has two children. Let's find out who is the uncle.
+    if (this.nodeComparator.equal(this.parent, this.parent.parent.left)) {
+      // Right one is an uncle.
+      return this.parent.parent.right;
+    }
+
+    // Left one is an uncle.
+    return this.parent.parent.left;
+  }
+
   /**
    * @param {BinaryTreeNode} node
    * @return {BinaryTreeNode}
diff --git a/src/data-structures/tree/__test__/BinaryTreeNode.test.js b/src/data-structures/tree/__test__/BinaryTreeNode.test.js
@@ -207,4 +207,54 @@ describe('BinaryTreeNode', () => {
     expect(redNode.meta.get('color')).toBe('red');
     expect(blackNode.meta.get('color')).toBe('black');
   });
+
+  it('should detect right uncle', () => {
+    const grandParent = new BinaryTreeNode('grand-parent');
+    const parent = new BinaryTreeNode('parent');
+    const uncle = new BinaryTreeNode('uncle');
+    const child = new BinaryTreeNode('child');
+
+    expect(grandParent.uncle).not.toBeDefined();
+    expect(parent.uncle).not.toBeDefined();
+
+    grandParent.setLeft(parent);
+
+    expect(parent.uncle).not.toBeDefined();
+    expect(child.uncle).not.toBeDefined();
+
+    parent.setLeft(child);
+
+    expect(child.uncle).not.toBeDefined();
+
+    grandParent.setRight(uncle);
+
+    expect(parent.uncle).not.toBeDefined();
+    expect(child.uncle).toBeDefined();
+    expect(child.uncle).toEqual(uncle);
+  });
+
+  it('should detect left uncle', () => {
+    const grandParent = new BinaryTreeNode('grand-parent');
+    const parent = new BinaryTreeNode('parent');
+    const uncle = new BinaryTreeNode('uncle');
+    const child = new BinaryTreeNode('child');
+
+    expect(grandParent.uncle).not.toBeDefined();
+    expect(parent.uncle).not.toBeDefined();
+
+    grandParent.setRight(parent);
+
+    expect(parent.uncle).not.toBeDefined();
+    expect(child.uncle).not.toBeDefined();
+
+    parent.setRight(child);
+
+    expect(child.uncle).not.toBeDefined();
+
+    grandParent.setLeft(uncle);
+
+    expect(parent.uncle).not.toBeDefined();
+    expect(child.uncle).toBeDefined();
+    expect(child.uncle).toEqual(uncle);
+  });
 });
