Implementing Binary Search Tree (BST) data structure in JavaScript
Nov 25, 2023
5 min read
Lets start from the most obvious question in this context;
What are data structures in programming?
In computer science, a data structure is a format to organize, manage and store data in a way that allows efficient access and modification.
Data structures are the most basic concept of any programming language that help us play with data. We store data in different data types based on the data and what we want to do with it.
For instance, if you want to store user form input, you would like to store it as an object as key value pairs, with keys being input name and value being the user input. If you want to store list of choices by user, i don't know about you, but I would store it as an array.
Different datastructures store data in a different way, work on that data in its own way, and expose data in a unique manner too. Lets have a look at Binary Search Tree data structure.
Binary Search Tree (BST) data structure:
A BST is a data structure used in computer science for organizing and storing data in a sorted manner. Each node in a Binary Search Tree has at most two children, a left child and a right child, with the left child containing values less than the parent node and the right child containing values greater than the parent node. This hierarchical structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree.
Implementation:
Lets start by creating a JavaScript ES6 Classes.
TreeNode Class: To create new nodes to add to the search tree.
Binary Search Tree Class: We will define a constructor function to initialize root node, and the size property of BST. We need to keep appending new nodes to the left side if it is smaller than active node, and to the right if it is greater.
BST methods:
Now lets add some methods to our class, to add node, remove node, and some utility methods to work with BST.
Add Data (insert):
insert: Inserts new nodes to the search tree.
1class BinarySearchTree {
2 constructor() {
3 this.root = null;
4 this.size = 0;
5 }
6
7 insert(value) {
8 let newNode = new TreeNode(value);
9 // check if tree contains any nodes before
10
11 if (this.root === null) {
12 // check if root exists
13 // we compare it to null, because it could be zero
14 // we dont want false postive comparison
15
16 // set root = new node
17 this.root = newNode;
18 this.size++;
19 return this;
20 }
21
22 // set active
23 let activeRoot = this.root;
24
25 while (true) {
26 // run infinite loop to itterate over bst nodes.
27
28 if (value === activeRoot.value) {
29 // if new value is equal to active node value
30 return this;
31 }
32
33 // check if new node belongs to left or right of the root
34 if (value < activeRoot.value) {
35 // belongs to left
36
37 if (activeRoot.left === null) {
38 // if not more nodes to the left
39 // set left to new node
40 // infinite itteration ends
41 activeRoot.left = newNode;
42 this.size++;
43 return this;
44 }
45
46 // otherwise keep setting activeRoot = left of activeRoot
47 // untill we encounter null (satisfies above if condition)
48 activeRoot = activeRoot.left;
49 } else if (value > activeRoot.value) {
50 // belongs to right
51 if (activeRoot.right === null) {
52 // if not more nodes to the right
53 // set right to new node
54 // infinite itteration ends
55 activeRoot.right = newNode;
56 this.size++;
57 return this;
58 }
59
60 // otherwise keep setting activeRoot = right of activeRoot
61 // until we encounter null (satisfies above if condition)
62 activeRoot = activeRoot.right;
63 } else {
64 return this;
65 }
66 }
67 }
68}Search BST (lookup, treeMinValue, treeMaxValue):
loopup: lookup methods finds us a specified node.
treeMinValue: Finds smallest node in the tree.
treeMaxValue: Finds largest node in the tree.
1class BinarySearchTree {
2 // ...
3
4 lookup(value) {
5 if (this.root === null) {
6 return undefined;
7 }
8
9 // set active root variable = current root
10 let activeRootNode = this.root;
11
12 while (true) {
13 // itterate infinitly over tree nodes
14
15 if (value === activeRootNode.value) {
16 // found: return activeRootNode
17 return activeRootNode;
18 }
19
20 // compare and find out to which side target node belongs
21 if (value < activeRootNode.value) {
22 // belongs to left
23 if (activeRootNode.left === null) {
24 // reach end: no more smaller nodes
25 // not found
26 return undefined;
27 }
28
29 // keep setting active root node = left of current active root node
30 activeRootNode = activeRootNode.left;
31 } else if (value > activeRootNode.value) {
32 // belongs to right
33 if (activeRootNode.right === null) {
34 // reach end: no more bigger nodes
35 // not found
36 return undefined;
37 }
38
39 // keep setting active root node = right of current active root node
40 activeRootNode = activeRootNode.right;
41 } else {
42 return undefined;
43 }
44 }
45 }
46
47 minValueNode() {
48 let activeRootNode = this.root;
49 // itterate infinitly over tree nodes
50 while (true) {
51 // until we have reach tree left end (no more smaller nodes)
52 if (activeRootNode.left === null) return activeRootNode;
53
54 // keep setting active root node = left of current active root node
55 activeRootNode = activeRootNode.left;
56 }
57 }
58
59 maxValueNode() {
60 let activeRootNode = this.root;
61 // itterate infinitly over tree nodes
62 while (true) {
63 // until we have reach tree right end (no more bigger nodes)
64 if (activeRootNode.right === null) return activeRootNode;
65
66 // keep setting active root node = right of current active root node
67 activeRootNode = activeRootNode.right;
68 }
69 }
70
71}Complete implementation and usage:
1class TreeNode {
2 constructor(value) {
3 this.left = null;
4 this.right = null;
5 this.value = value;
6 }
7}
8class BinarySearchTree {
9 constructor() {
10 this.root = null;
11 this.size = 0;
12 }
13
14 insert(value) {
15 let newNode = new TreeNode(value);
16 // check if tree contains any nodes before
17
18 if (this.root === null) {
19 // check if root exists
20 // we compare it to null, because it could be zero
21 // we dont want false postive comparison
22
23 // set root = new node
24 this.root = newNode;
25 this.size++;
26 return this;
27 }
28
29 // set active
30 let activeRoot = this.root;
31
32 while (true) {
33 // run infinite loop to itterate over bst nodes.
34
35 if (value === activeRoot.value) {
36 // if new value is equal to active node value
37 return this;
38 }
39
40 // check if new node belongs to left or right of the root
41 if (value < activeRoot.value) {
42 // belongs to left
43
44 if (activeRoot.left === null) {
45 // if not more nodes to the left
46 // set left to new node
47 // infinite itteration ends
48 activeRoot.left = newNode;
49 this.size++;
50 return this;
51 }
52
53 // otherwise keep setting activeRoot = left of activeRoot
54 // untill we encounter null (satisfies above if condition)
55 activeRoot = activeRoot.left;
56 } else if (value > activeRoot.value) {
57 // belongs to right
58 if (activeRoot.right === null) {
59 // if not more nodes to the right
60 // set right to new node
61 // infinite itteration ends
62 activeRoot.right = newNode;
63 this.size++;
64 return this;
65 }
66
67 // otherwise keep setting activeRoot = right of activeRoot
68 // until we encounter null (satisfies above if condition)
69 activeRoot = activeRoot.right;
70 } else {
71 return this;
72 }
73 }
74 }
75
76 lookup(value) {
77 if (this.root === null) {
78 return undefined;
79 }
80
81 // set active root variable = current root
82 let activeRootNode = this.root;
83
84 while (true) {
85 // itterate infinitly over tree nodes
86
87 if (value === activeRootNode.value) {
88 // found: return activeRootNode
89 return activeRootNode;
90 }
91
92 // compare and find out to which side target node belongs
93 if (value < activeRootNode.value) {
94 // belongs to left
95 if (activeRootNode.left === null) {
96 // reach end: no more smaller nodes
97 // not found
98 return undefined;
99 }
100
101 // keep setting active root node = left of current active root node
102 activeRootNode = activeRootNode.left;
103 } else if (value > activeRootNode.value) {
104 // belongs to right
105 if (activeRootNode.right === null) {
106 // reach end: no more bigger nodes
107 // not found
108 return undefined;
109 }
110
111 // keep setting active root node = right of current active root node
112 activeRootNode = activeRootNode.right;
113 } else {
114 return undefined;
115 }
116 }
117 }
118
119 treeMinValue() {
120 let activeRootNode = this.root;
121 // itterate infinitly over tree nodes
122 while (true) {
123 // until we have reach tree left end (no more smaller nodes)
124 if (activeRootNode.left === null) return activeRootNode;
125
126 // keep setting active root node = left of current active root node
127 activeRootNode = activeRootNode.left;
128 }
129 }
130
131 treeMaxValue() {
132 let activeRootNode = this.root;
133 // itterate infinitly over tree nodes
134 while (true) {
135 // until we have reach tree right end (no more bigger nodes)
136 if (activeRootNode.right === null) return activeRootNode;
137
138 // keep setting active root node = right of current active root node
139 activeRootNode = activeRootNode.right;
140 }
141 }
142}
143
144let tree = new BinarySearchTree();
145
146tree.insert(45);
147tree.insert(15);
148tree.insert(79);
149tree.insert(90);
150tree.insert(10);
151tree.insert(55);
152tree.insert(12);
153console.log(tree.lookup(90)); // { left: null, right: null, value: 90 }
154console.log(tree.lookup(100)); // undefined
155console.log(tree.treeMinValue()); // 10
156console.log(tree.treeMaxValue()); // 90
157Have a good day. See you in the the next one.