Implementing a Binary Search Tree in Javascript
Eniola Bakare
A tree is a hierarchical data structure with a set of connected nodes. A family tree or an organogram comes to mind easily. With this data structure, there is a parent-child relationship between an ancestor node and a child node, and these relationships/connections are called edges.
A key distinction between a tree DS and a graph is that there are no connections between sibling nodes in a tree. Where any such connection exists, the tree becomes a graph, hence the proposition that trees are a type of graph without circles, and vice versa.
https://www.30secondsofcode.org/js/s/data-structures-binary-search-tree/
Key Words in a Tree DS:
Root: this is the ancestor node with no other parent or source; it is the origin of the tree; in the tree above, the node with the value of 30 is the root node;
Parent: this is a direct ancestor of another node, called the child node; node 10 is a child node of node 30, and node 40 is the parent node of node 35.
Leaf node: this is a node without any child node; just like leaves hang down from an actual tree. Node 12, 35, and 50 are examples of leaf nodes;
Height: is the number of edges between the root node and the farthest leaf node. The tree above has a height of 3;
Depth: is the distance between a particular node and the root node. The depth of node 35 is 2;
Siblings: these are nodes that share the same parent, hence, nodes 10 and 40, and nodes 35 and 50 are sibling nodes respectively.
Types of Tree DS:
There are various types of trees DS and various ways a tree DS can be represented. The common types of trees include a general tree, binary tree, binary search tree, heap, balanced binary tree, etc.
Tree nodes can have multiple children nodes. However when the number of nodes is limited to just two, then there is a binary tree.
When the two children nodes in a binary tree follow a specific order: where the lower child value is placed on the left of its parent node, and the higher child node value is placed on the right, then there is a binary search tree. And if you remember the pre-condition for a binary search algorithm, that the values must be ordered, then you realize a binary search tree helps achieve this order, as a precondition for the binary search algorithm.
As an abstract data structure, there are various ways to represent a tree data structure, while utilizing other data structures, such as a linked list, an array, adjacency matrix, or adjacency list. In this article, we will use the linked list data structure.
Operations on a Tree:
Just like other data structures, a tree allows insertion, removal, searching and traversal. Each of these operation will be implemented with a binary search tree, which is a common type of tree.
1. Insertion
There are three (3) steps to insert a node into a tree data structure:
check if it’s an empty tree, if so add the new value as the root node for the tree;
else, if the value to be added is greater than the root node, check if the right pointer of the root node is null and add it there. If it is lower than the root node, check if the left pointer of the root node is empty and add it there.
Where the left or right pointer is not null, do step 2 repeatedly, taking the current node as the root node, until there is an empty slot for the new node.
// Insertion in a Binary Search Tree with a linked list
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
//1. Account for an empty list
if (this.root === null) {
this.root = new TreeNode(value);
return this.root;
}
// 2. Where the tree is not empty:
// recursively check if the value is greater or lesser
// than the current node, to determine where to place the new node.
function placer(root, value) {
// if the current value is greater than the current node's value,
// thread the right child to satisfy the order of a BST
if (value > root.value) {
if (root.right === null) {
// 3. check if the current node's right is
// empty and place the new node there
root.right = new TreeNode(value);
} else {
// 4. where the current's node is not empty,
// recursively check again if it is greater or
// lesser than the current node
placer(root.right, value);
}
}
// if the current value is lesser than the current node's value,
// thread the left child to satisfy the order of a BST
if (value < root.value) {
// if the current node's left is
// empty, the new node there
if (root.left === null) {
root.left = new TreeNode(value);
} else {
// where the current's node is not empty,
// recursively check again if it is greater or
// lesser than the current node
placer(root.left, value);
}
}
}
placer(this.root, value);
return this.root;
}
}
const newBST = new BinarySearchTree();
newBST.insert(45);
newBST.insert(40);
newBST.insert(75);
newBST.insert(50);
newBST.insert(30);
newBST.insert(43);
newBST.insert(80);
console.log(newBST.root);
// the tree looks like this:
// 45
// / \\
// 40 75
// / \\ / \\
// 30 43 50 80
// {
// "value": 45,
// "left": {
// "value": 40,
// "left": {
// "value": 30,
// "left": null,
// "right": null
// },
// "right": {
// "value": 43,
// "left": null,
// "right": null
// }
// },
// "right": {
// "value": 75,
// "left": {
// "value": 50,
// "left": null,
// "right": null
// },
// "right": {
// "value": 80,
// "left": null,
// "right": null
// }
// }
// }
An illustration of a Binary Search Tree after insertions
2. Searching
In searching through a binary search tree, you traverse either the left or right child node depending on the value being sought.
If the value is greater than the current’s node value, check its right child. If its the value sought, the search ends, if its lesser than the value sought, you check its right, if it is greater than the value sought, you check its left child node, and continue until you find the value or get to the end of the tree, signified by reaching a leaf node.
// Searching in a Binary Search Tree
search(root, value) {
// where the root node is null, either from traversing the entire tree
// until the end, or by default as an empty tree, it means the node isn't ther
if (root === null) {
console.log("Value not found !");
return null
} else {
// where the value is equal to the current node's value,
// the sought value is found !
if (value === root.value) {
console.log("FOUND/!");
return root.value;
} else if (value > root.value) {
// where the value is greater than the current node's value, check its right
return this.search(root.right, value);
} else {
// where the value is greater than the current node's value, check its left
return this.search(root.left, value);
}
}
}
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
if (this.root === null) {
this.root = new TreeNode(value);
return this.root;
function placer(root, value) {
if (value > root.value) {
if (root.right === null) {
root.right = new TreeNode(value);
} else {
placer(root.right, value);
}
}
if (value < root.value) {
if (root.left === null) {
root.left = new TreeNode(value);
} else {
placer(root.left, value);
}
}
}
placer(this.root, value);
return this.root;
}
search(root, value) {
if (root === null) {
console.log("Value not found !");
return;
} else {
if (value === root.value) {
console.log("FOUND!");
return root.value;
} else if (value > root.value) {
this.search(root.right, value);
} else {
this.search(root.left, value);
}
}
}
}
const newBST = new BinarySearchTree();
newBST.insert(45);
newBST.insert(40);
newBST.insert(75);
newBST.insert(50);
newBST.insert(30);
newBST.insert(43);
newBST.insert(80);
console.log(newBST.root);
// the tree looks like this:
// 45
// / \\
// 40 75
// / \\ / \\
// 30 43 50 80
console.lognewBST.search((newBST.root, 3));
// for this operation, the function first checks the root node(45)
// 1. it is not empty
// 2. the sought value (3) is lesser than the root node, so it goes to
// its left child (40)
// 3. repeats step 2 and goes to the next left child (30)
// 4. because the node's value (30) is a leaf node, there's no lesser
// option to explore, then it returns:
// "Value not found !"
// null
console.log(newBST.search(newBST.root, 30));
// for this operation, the function first checks the root node(45)
// 1. it is not empty
// 2. the sought value (3) is lesser than the root node, so it goes to
// its left child (40), using it as the root node
// 3. repeats step 2 and goes to the next left child (30),
// which is eaqual to the sort value, which returns:
// "FOUND!"
// 30
3. Traversal
Traversing a tree means visiting every node in the tree. This can take different forms, such as visiting the root node first, its left child node, then its right child, or in any other direction. Two common patterns of traversal are: i. Depth First Search ii. Breadth-First Search
DFS Traversal
In a Depth First Search, you visit a strand of the tree to its farthest leaf node before visiting the other strand, and it can happen in three different orders:
Pre-order traversal → visit the root node first, then its left strand to the farthest, then its right strand. A Root first, then left to right child policy.
// 1. Pre-order traversal in BST preorder(root) { if (!root) return; // breaks out of the recursive function at the end console.log(root.value); // prints the root value first this.preorder(root.left); // visits the left values and prints them this.preorder(root.right); // visits the right values and prints them }In-order traversal → visit the left node first, then the root node, before the right node. A left first, then root to right child policy. This traversal visits the tree in an ascending order.
// In-order traversal in BST inorder(root) { if (!root) return; // breaks out of the recursive function at the end this.inorder(root.left); // visits the left values console.log(root.value) // prints the root value next this.inorder(root.right); // visits the right values }Post-order traversal → visits the left child first, then the right child before the root node. A left first, then right child to root node policy.
// Post-order traversal in BST postOrder(root) { if (!root) return; // breaks out of the recursive function at the end this.postOrder(root.left); // visits the left values this.postOrder(root.right); // visits the right values console.log(root.value); // prints the root value }class TreeNode { constructor(value) { this.value = value; this.left = null; this.right = null; } } class BinarySearchTree { constructor() { this.root = null; } insert(value) { if (this.root === null) { this.root = new TreeNode(value); return this.root; function placer(root, value) { if (value > root.value) { if (root.right === null) { root.right = new TreeNode(value); } else { placer(root.right, value); } } if (value < root.value) { if (root.left === null) { root.left = new TreeNode(value); } else { placer(root.left, value); } } } placer(this.root, value); return this.root; } search(root, value) { if (root === null) { console.log("Value not found !"); return; } else { if (value === root.value) { console.log("FOUND!"); return root.value; } else if (value > root.value) { this.search(root.right, value); } else { this.search(root.left, value); } } } preOrder(root) { if (!root) return; console.log(root.value); this.preorder(root.left); this.preorder(root.right); } inOrder(root) { if (!root) return; this.inorder(root.left); console.log(root.value); this.inorder(root.right); } postOrder(root) { if (!root) return; this.postOrder(root.left); this.postOrder(root.right); console.log(root.value); } } const newBST = new BinarySearchTree(); newBST.insert(45); newBST.insert(40); newBST.insert(75); newBST.insert(50); newBST.insert(30); newBST.insert(43); newBST.insert(80); newBST.preorder(newBST.root): // will print the values of the tree in this order: 45 40 30 43 75 50 80 newBST.inorder(newBST.root): // will print the values of the tree in this order: 30 40 43 45 50 75 80 newBST.postOrder(newBST.root): // will print the values of the tree in this order: 30 43 40 50 80 75 45→ It’s worth noting that these operations will follow the same order for subtrees until all values are printed; it will recursively traverse subtrees, if available.
BFS
In a breadth-first traversal, as the name implies, we visit all the nodes on the same level, which are at the same depth, before moving to the next level of depth.
To achieve this:
create a queue
add (enqueue) the root node
as long as the queue is not empty,
dequeue the queue from the front
read its value
enqueue its left and child nodes into the queue
// BFS traversal in a Binary Search Tree
BST(root) {
const queue = []; // creates a queue
queue.push(root); // enqueues the root node
while (queue.length > 0) { // iterates while the queue is not empty
const node = queue.shift(); // dequeues the first node
console.log(node.value); // reads the value of the first node
if (node.left) {
queue.push(node.left); // enqueues the left child if any
}
if (node.right) {
queue.push(node.right); // enqueues the right child if any
}
}
}
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
if (this.root === null) {
this.root = new TreeNode(value);
return this.root;
function placer(root, value) {
if (value > root.value) {
if (root.right === null) {
root.right = new TreeNode(value);
} else {
placer(root.right, value);
}
}
if (value < root.value) {
if (root.left === null) {
root.left = new TreeNode(value);
} else {
placer(root.left, value);
}
}
}
placer(this.root, value);
return this.root;
}
search(root, value) {
if (root === null) {
console.log("Value not found !");
return;
} else {
if (value === root.value) {
console.log("FOUND!");
return root.value;
} else if (value > root.value) {
this.search(root.right, value);
} else {
this.search(root.left, value);
}
}
}
preOrder(root) {
if (!root) return;
console.log(root.value);
this.preorder(root.left);
this.preorder(root.right);
}
inOrder(root) {
if (!root) return;
this.inorder(root.left);
console.log(root.value);
this.inorder(root.right);
}
postOrder(root) {
if (!root) return;
this.postOrder(root.left);
this.postOrder(root.right);
console.log(root.value);
}
BST(root) {
const queue = []; // creates a queue
queue.push(root); // enqueues the root node
while (queue.length > 0) { // iterates while the queue is not empty
const node = queue.shift(); // dequeues the first node
console.log(node.value); // reads the value of the first node
if (node.left) {
queue.push(node.left); // enqueues the left child if any
}
if (node.right) {
queue.push(node.right); // enqueues the right child if any
}
}
}
}
const newBST = new BinarySearchTree();
newBST.insert(45);
newBST.insert(40);
newBST.insert(75);
newBST.insert(50);
newBST.insert(30);
newBST.insert(43);
newBST.insert(80);
// at this point, the tree looks like this:
// 45
// / \\
// 40 75
// / \\ / \\
// 30 43 50 80
newBST.BST(newBST.root):
// this Breadth First Search operation will visit the nodes in this order:
// 45 ->
// 40 -> 75
// 30 -> 43 -> 50 -> 80
4. Removal
In removing a node, there are three conditions to account for, when removing
a node with no child;
a node with one child;
a node with two children;
// Removal in a Binary Search Tree
findMin(root) {
while (root.left) {
root = root.left;
}
return root.value;
}
delete(root, value) {
if (!root) return root; //Base case: return if the tree is empty or
// iteration has reached the leaf node without finding the value to be deleted
if (value > root.value) {
// iterate recursively on the right side
// if the value is greater than the current node being checked
root.right = this.delete(root.right, value);
} else if (value < root.value) {
// iterate recursively on the left side
// if the value is lesser than the current node being checked
root.left = this.delete(root.left, value);
} else {
// it enters this block when the above conditions fail,
// implying the value matches the current node being checked.
// Here we'll address the three possible situations highlighted above:
// 1. situation one, where the node has no children:
// return null
if (!root.left && !root.right) {
return null;
}
// 2. situation two: where the node has one child:
// replace the deleted node with the child
if (!root.right) {
return root.left;
}
if (!root.left) {
return root.right;
}
// 3. situation three: where the node has two children:
// replace the node with the in-order right child,
// which is the minimum value to it's right, and delete the right node
root.value = this.findMin(root.right);
root.right = this.delete(root.right, root.value);
}
return root;
}
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
if (this.root === null) {
this.root = new TreeNode(value);
return this.root;
function placer(root, value) {
if (value > root.value) {
if (root.right === null) {
root.right = new TreeNode(value);
} else {
placer(root.right, value);
}
}
if (value < root.value) {
if (root.left === null) {
root.left = new TreeNode(value);
} else {
placer(root.left, value);
}
}
}
placer(this.root, value);
return this.root;
}
search(root, value) {
if (root === null) {
console.log("Value not found !");
return;
} else {
if (value === root.value) {
console.log("FOUND!");
return root.value;
} else if (value > root.value) {
this.search(root.right, value);
} else {
this.search(root.left, value);
}
}
}
preOrder(root) {
if (!root) return;
console.log(root.value);
this.preorder(root.left);
this.preorder(root.right);
}
inOrder(root) {
if (!root) return;
this.inorder(root.left);
console.log(root.value);
this.inorder(root.right);
}
postOrder(root) {
if (!root) return;
this.postOrder(root.left);
this.postOrder(root.right);
console.log(root.value);
}
BST(root) {
const queue = []; // creates a queue
queue.push(root); // enqueues the root node
while (queue.length > 0) { // iterates while the queue is not empty
const node = queue.shift(); // dequeues the first node
console.log(node.value); // reads the value of the first node
if (node.left) {
queue.push(node.left); // enqueues the left child if any
}
if (node.right) {
queue.push(node.right); // enqueues the right child if any
}
}
}
}
const newBST = new BinarySearchTree();
newBST.insert(45);
newBST.insert(40);
newBST.insert(75);
newBST.insert(50);
newBST.insert(30);
newBST.insert(43);
newBST.insert(80);
// at this point, the tree looks like this:
// 45
// / \
// 40 75
// / \ / \
// 30 43 50 80
console.log(newBST.delete(newBST.root, 30));
// returns the tree as this:
// 45
// / \\
// 40 75
// / \\ / \\
// 43 50 80
console.log(newBST.delete(newBST.root, 75));
// 45
// / \\
// 40 80
// / \\ /
// 43 50
Time Complexity:
The time complexity for the operations on a tree will usually be O(log n), just as in a binary search algorithm, where half of the tree is discarded at each iteration, given that the value to be added or deleted can either be on one half of the tree.
However, the TC of O(log n) can swiftly degenerate from a O(log n) into O(n), where the tree becomes unbalanced.
https://adrianmejia.com/data-structures-for-beginners-trees-binary-search-tree-tutorial/
Conclusion
Binary Search Trees (BSTs) are really important in computer science because they make operations like searching, inserting, and deleting data a lot faster, especially when the data is sorted. With a good structure, BSTs help us look things up quickly, usually in O(log n) time for balanced trees. But, if the tree gets unbalanced, the performance can drop to O(n).
When deleting nodes in a BST, you have to handle three different cases: when a node has no children, one child, or two children. Each case needs its own solution to keep the tree working properly.
Trees aren’t just for BSTs; they’re super useful in many other areas, like algorithms, databases, and even machine learning, where they help with decision-making, organizing data, and more.
Extra Resources
Subscribe to my newsletter
Read articles from Eniola Bakare directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
Eniola Bakare
Eniola Bakare
As a graduate of Law, however, with an interest in computers and how they work, and particularly software development, this is a hub spot for my technical learnings.