Binary Trees 🎄
Description:
A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left and right child. It's a key data structure for implementing search trees like binary search trees.
Pros & Cons:
Using this data structure has some benefits, such as:
Efficient Searching: Search operations can be done in O(log n) time in a balanced binary search tree.
Insertion & Deletion: Both can be done efficiently, with O(log n) in the average case for a balanced tree.
It also has some cons, for example:
Unbalanced Trees: If the tree becomes unbalanced, operations degrade to O(n), which is the same as a linked list.
Memory Usage: Each node needs to store references to both left and right children, which adds to the memory overhead.
1. Inserting into the Binary Tree:
The insert function allows us to add new nodes into the binary tree. The new node is added in the correct position to maintain the binary search tree property: left child nodes have smaller values, and right child nodes have larger values.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
insert(nodeToInsert: TreeNode) {
if (!this.head) {
this.head = nodeToInsert;
} else {
this.insertHelper(nodeToInsert, this.head);
}
}
private insertHelper(nodeToInsert: TreeNode, node: TreeNode) {
if (nodeToInsert.value === node.value) {
console.error("Cannot add a duplicated node");
return;
}
if (nodeToInsert.value < node.value) {
if (node.left) {
this.insertHelper(nodeToInsert, node.left);
} else {
node.left = nodeToInsert;
}
} else {
if (node.right) {
this.insertHelper(nodeToInsert, node.right);
} else {
node.right = nodeToInsert;
}
}
}
2. Searching for Nodes:
The search function allows us to find a node in the tree by its value. It traverses the tree to the left or right based on the target value.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
search(value: number): TreeNode | null {
if (this.head) {
return this.searchHelper(value, this.head);
}
return null;
}
private searchHelper(value: number, node: TreeNode): TreeNode | null {
if (value === node.value) {
return node;
} else if (value < node.value) {
if (node.left) return this.searchHelper(value, node.left);
} else {
if (node.right) return this.searchHelper(value, node.right);
}
return null;
}
3. Deleting Nodes:
The delete function removes a node from the binary tree. It handles three cases: (1) deleting a leaf node, (2) deleting a node with one child, and (3) deleting a node with two children.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
delete(value: number) {
if (this.head) {
this.deleteHelper(value, this.head);
} else {
console.log(`Value ${value} - Not found to delete`);
}
}
private deleteHelper(value: number, node: TreeNode): TreeNode | null {
if (value === node.value) {
if (!node.left && !node.right) return null;
if (!node.left) return node.right;
if (!node.right) return node.left;
const successor = this.successor(node);
if (successor) {
node.value = successor.value;
node.right = this.deleteHelper(successor.value, node.right);
}
return node;
} else if (value < node.value) {
if (node.left) node.left = this.deleteHelper(value, node.left);
} else {
if (node.right) node.right = this.deleteHelper(value, node.right);
}
return node;
}
4. Finding Successor and Predecessor:
The successor is the smallest node greater than the current node, and the predecessor is the largest node smaller than the current node. These functions help in identifying the next node in an in-order traversal.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
successor(node: TreeNode): TreeNode | null {
if (node.right) {
let successor = node.right;
while (successor.left) {
successor = successor.left;
}
return successor;
}
return null;
}
predecessor(node: TreeNode): TreeNode | null {
if (node.left) {
let predecessor = node.left;
while (predecessor.right) {
predecessor = predecessor.right;
}
return predecessor;
}
return null;
}
Testing the Implementation
Now that we have explained all the components, let’s see them in action:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// Create a new binary tree.
const binaryTree = new BinaryTree();
/* Inserting the following data:
* | | | | | | |7 | | | | |
* | | | | | |/ | |\ | | | |
* | | | | |5 | | | |9 | | |
* | | | |/ | |\ | | | |\ | |
* | | |3 | | | |6 | | | |15|
* | |/ | | | | | | | |/ | |
* |1 | | | | | | | |12| | |
* */
console.log('** Insert elements in this order: 7,5,3,9,6,15,1,12,11,10');
binaryTree.insert({ value: 7 } as TreeNode);
binaryTree.insert({ value: 5 } as TreeNode);
binaryTree.insert({ value: 3 } as TreeNode);
binaryTree.insert({ value: 9 } as TreeNode);
binaryTree.insert({ value: 6 } as TreeNode);
binaryTree.insert({ value: 15 } as TreeNode);
binaryTree.insert({ value: 1 } as TreeNode);
binaryTree.insert({ value: 12 } as TreeNode);
binaryTree.insert({ value: 11 } as TreeNode);
binaryTree.insert({ value: 10 } as TreeNode);
// Show the tree in ASCII form
console.log('** Ascii display of the tree');
binaryTree.showAscii(binaryTree.head);
// Search for a node that is in the tree
console.log('** Search for node with value: 3');
const firstSearchNode = binaryTree.search(3);
console.log('*** Result: ', firstSearchNode);
// Search for a node that is NOT in the tree
console.log('** Search for node with value: 20 (not in the tree)');
const secondSearchNode = binaryTree.search(20);
console.log('*** Result: ', secondSearchNode);
const toFind = binaryTree.search(7);
if (toFind) {
// Find predecessor - highest value in the left subtree.
const predecessor = binaryTree.predecessor(toFind);
console.log('** Search for predecessor of: 7');
console.log('*** Result: ', predecessor?.value);
// Find successor - smallest value in the right subtree.
const successor = binaryTree.successor(toFind);
console.log('** Search for sucessor of: 7');
console.log('*** Result: ', successor?.value);
}
console.log('** Deleting vlaue: 5');
binaryTree.delete(5);
console.log('** Ascii display of the tree');
binaryTree.showAscii(binaryTree.head);
You should see something like the following in the console:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
** Insert elements in this order: 7,5,3,9,6,15,1,12,11,10
** Ascii display of the tree
7
/ \
5 9
/ \ \
3 6 15
/ /
1 12
/
11
/
10
** Search for node with value: 3
*** Result: {value: 3, left: {…}}
** Search for node with value: 20 (not in the tree)
*** Result: null
** Search for predecessor of: 7
*** Result: 6
** Search for sucessor of: 7
*** Result: 9
** Deleting vlaue: 5
Value 5 - Not found to delete
** Ascii display of the tree
7
/ \
6 9
/ \
3 15
/ /
1 12
/
11
/
10
Complete Binary Tree Implementation
Here is the full implementation of the binary tree for you to copy:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
export type TreeNode = {
value: number;
left: TreeNode | null;
right: TreeNode | null;
};
export class BinaryTree {
head: TreeNode | null = null;
insert(nodeToInsert: TreeNode) {
if (!this.head) {
this.head = nodeToInsert;
} else {
this.insertHelper(nodeToInsert, this.head);
}
}
private insertHelper(nodeToInsert: TreeNode, node: TreeNode) {
if (nodeToInsert.value === node.value) {
console.error("Cannot add a duplicated node");
return;
}
if (nodeToInsert.value < node.value) {
if (node.left) {
this.insertHelper(nodeToInsert, node.left);
} else {
node.left = nodeToInsert;
}
} else {
if (node.right) {
this.insertHelper(nodeToInsert, node.right);
} else {
node.right = nodeToInsert;
}
}
}
search(value: number): TreeNode | null {
if (this.head) {
return this.searchHelper(value, this.head);
}
return null;
}
private searchHelper(value: number, node: TreeNode): TreeNode | null {
if (value === node.value) {
return node;
} else if (value < node.value) {
if (node.left) return this.searchHelper(value, node.left);
} else {
if (node.right) return this.searchHelper(value, node.right);
}
return null;
}
delete(value: number) {
if (this.head) {
this.deleteHelper(value, this.head);
} else {
console.log(`Value ${value} - Not found to delete`);
}
}
private deleteHelper(value: number, node: TreeNode): TreeNode | null {
if (value === node.value) {
if (!node.left && !node.right) return null;
if (!node.left) return node.right;
if (!node.right) return node.left;
const successor = this.successor(node);
if (successor) {
node.value = successor.value;
node.right = this.deleteHelper(successor.value, node.right);
}
return node;
} else if (value < node.value) {
if (node.left) node.left = this.deleteHelper(value, node.left);
} else {
if (node.right) node.right = this.deleteHelper(value, node.right);
}
return node;
}
successor(node: TreeNode): TreeNode | null {
if (node.right) {
let successor = node.right;
while (successor.left) {
successor = successor.left;
}
return successor;
}
return null;
}
predecessor(node: TreeNode): TreeNode | null {
if (node.left) {
let predecessor = node.left;
while (predecessor.right) {
predecessor = predecessor.right;
}
return predecessor;
}
return null;
}
}