Skip to content

Commit 5a59d27

Browse files
GapurGapur
committed
feat(tree): implement binary-tree-node
1 parent 7d88ba4 commit 5a59d27

File tree

3 files changed

+194
-0
lines changed

3 files changed

+194
-0
lines changed

‎data-structures/index.js

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,11 +3,13 @@ const Queue = require('./queue');
33
const Stack = require('./stack');
44
const Heap = require('./heap');
55
const HashTable = require('./hash-table');
6+
const BinaryTreeNode = require('./tree');
67

78
module.exports = {
89
LinkedList,
910
Queue,
1011
Stack,
1112
Heap,
1213
HashTable,
14+
BinaryTreeNode,
1315
};

‎data-structures/tree/BinaryTreeNode.js

Lines changed: 163 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,163 @@
1+
const HashTable = require('../hash-table/HashTable');
2+
3+
module.exports = class BinaryTreeNode {
4+
constructor(value = null) {
5+
this.left = null;
6+
this.right = null;
7+
this.parent = null;
8+
this.value = value;
9+
10+
// Any node related meta information may be stored here.
11+
this.meta = new HashTable();
12+
}
13+
14+
get leftHeight() {
15+
if (!this.left) {
16+
return 0;
17+
}
18+
19+
return this.left.height + 1;
20+
}
21+
22+
get rightHeight() {
23+
if (!this.right) {
24+
return 0;
25+
}
26+
27+
return this.right.height + 1;
28+
}
29+
30+
get height() {
31+
return Math.max(this.leftHeight, this.rightHeight);
32+
}
33+
34+
get balanceFactor() {
35+
return this.leftHeight - this.rightHeight;
36+
}
37+
38+
get uncle() {
39+
// Check if current node has parent.
40+
if (!this.parent) {
41+
return undefined;
42+
}
43+
44+
// Check if current node has grand-parent.
45+
if (!this.parent.parent) {
46+
return undefined;
47+
}
48+
49+
// Check if grand-parent has two children.
50+
if (!this.parent.parent.left || !this.parent.parent.right) {
51+
return undefined;
52+
}
53+
54+
// So for now we know that current node has grand-parent and this
55+
// grand-parent has two children. Let's find out who is the uncle.
56+
if (this.parent === this.parent.parent.left) {
57+
// Right one is an uncle.
58+
return this.parent.parent.right;
59+
}
60+
61+
// Left one is an uncle.
62+
return this.parent.parent.left;
63+
}
64+
65+
setValue(value) {
66+
this.value = value;
67+
68+
return this;
69+
}
70+
71+
setLeft(node) {
72+
// Reset parent for left node since it is going to be detached.
73+
if (this.left) {
74+
this.left.parent = null;
75+
}
76+
77+
// Attach new node to the left.
78+
this.left = node;
79+
80+
// Make current node to be a parent for new left one.
81+
if (this.left) {
82+
this.left.parent = this;
83+
}
84+
85+
return this;
86+
}
87+
88+
setRight(node) {
89+
// Reset parent for right node since it is going to be detached.
90+
if (this.right) {
91+
this.right.parent = null;
92+
}
93+
94+
// Attach new node to the right.
95+
this.right = node;
96+
97+
// Make current node to be a parent for new right one.
98+
if (node) {
99+
this.right.parent = this;
100+
}
101+
102+
return this;
103+
}
104+
105+
removeChild(nodeToRemove) {
106+
if (this.left && this.left === nodeToRemove) {
107+
this.left = null;
108+
return true;
109+
}
110+
111+
if (this.right && this.right === nodeToRemove) {
112+
this.right = null;
113+
return true;
114+
}
115+
116+
return false;
117+
}
118+
119+
replaceChild(nodeToReplace, replacementNode) {
120+
if (!nodeToReplace || !replacementNode) {
121+
return false;
122+
}
123+
124+
if (this.left && this.left === nodeToReplace) {
125+
this.left = replacementNode;
126+
return true;
127+
}
128+
129+
if (this.right && this.right === nodeToReplace) {
130+
this.right = replacementNode;
131+
return true;
132+
}
133+
134+
return false;
135+
}
136+
137+
static copyNode(sourceNode, targetNode) {
138+
targetNode.setValue(sourceNode.value);
139+
targetNode.setLeft(sourceNode.left);
140+
targetNode.setRight(sourceNode.right);
141+
}
142+
143+
traverseInOrder() {
144+
let traverse = [];
145+
146+
if (this.left) {
147+
traverse = traverse.concat(this.left.traverseInOrder());
148+
}
149+
150+
// Add root.
151+
traverse.push(this.value);
152+
153+
if (this.right) {
154+
traverse = traverse.concat(this.right.traverseInOrder());
155+
}
156+
157+
return traverse;
158+
}
159+
160+
toString() {
161+
return this.traverseInOrder().toString();
162+
}
163+
};

‎data-structures/tree/index.js

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
const BinaryTreeNode = require('./BinaryTreeNode');
2+
3+
console.log('start BinaryTreeNode ------');
4+
5+
const node = new BinaryTreeNode();
6+
7+
console.log(`node=${node} value=${node.value} left=${node.left} right=${node.right}`);
8+
9+
const leftNode = new BinaryTreeNode(1);
10+
const rightNode = new BinaryTreeNode(3);
11+
const rootNode = new BinaryTreeNode(2);
12+
rootNode
13+
.setLeft(leftNode)
14+
.setRight(rightNode);
15+
16+
console.log(`node=${rootNode} value=${rootNode.value} left=${rootNode.left} right=${rootNode.right} left-parent=${rootNode.left.parent.value}`);
17+
18+
console.log(`node=${rootNode.toString()}`);
19+
20+
rootNode.removeChild(rootNode.left);
21+
22+
console.log(`node=${rootNode.toString()}`);
23+
24+
rootNode.setLeft(leftNode);
25+
rootNode.replaceChild(rootNode.right, rootNode.right.right);
26+
27+
console.log('end BinaryTreeNode ------');
28+
29+
module.exports = () => console.log('BinaryTreeNode is done');

0 commit comments

Comments
 (0)