# Binary Search Trees: The Knights of Data Kingdom - Part 2

### Part 9 of data structures series. Let’s build a Binary Search Tree 🌳 in JavaScript from scratch!

Hey there, fellow coder! 👋 Are you ready to get your hands dirty and start coding one of the coolest and most efficient data structures out there? Welcome to **Part 2** of our **Binary Search Tree (BST) adventure**, where we'll move from theory to practice. In this fun, interactive article, we’ll walk through how to **build a Binary Search Tree from scratch in JavaScript**.

We’ll take baby steps (because we all start as beginners) and explain every bit of code we write. By the end of this, you’ll be able to create your very own BST! Ready? Let’s go! 🚀

### 🧐 Quick Recap – What is a BST?

Before we dive into coding, let’s just remind ourselves what a Binary Search Tree is (super quick!):

It’s a binary tree, where each node has

**at most two children**(left and right).**Left child**nodes are always**smaller**than their parent node.**Right child**nodes are always**greater**than their parent node.This structure allows for

**fast lookups, insertions, and deletions**.

Got it? Cool! Now, time to code! 👨💻👩💻

### Step 1: Let’s Build a Node Class! 🧱

First things first, we need a **Node**. Think of a node as a box that holds two things:

The

**value**(the actual data).Pointers to the

**left**and**right**children.

Here’s the code to create a `Node`

class:

```
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
```

🕹 Challenge:Write out what each property in the`Node`

class represents! (Hint: What’s`left`

and`right`

for?)

### Step 2: The Binary Search Tree Class 🌳

Now that we have a `Node`

, it’s time to build the **Binary Search Tree (BST)** itself! This class will handle the key operations of **insertion, deletion, and search**. We'll focus on these three today, but don't worry—I’ll cover more advanced operations in the upcoming articles!

We’ll start by building the skeleton of our `BST`

class:

```
class BinarySearchTree {
constructor() {
this.root = null; // The starting point of our tree
}
// Insert a new node into the BST
insert(value) {
}
// Looking for a value in the BST
search(value) {
}
// removing a value (node) from the BST
remove(value) {
}
}
```

### Step 3: Insertion in a BST ➕

Let’s code the insert function now:

```
class BinarySearchTree {
constructor() {
this.root = null; // The starting point of our tree
}
// Insert a new node into the BST
insert(value) {
const newNode = new Node(value);
// if the tree is empty
if (this.root === null) {
// Tree is empty, make this the root
this.root = newNode;
} else {
// Helper function to place the node and keep code clean
this.insertNode(this.root, newNode);
}
}
// Helper function to handle the insertion recursively
insertNode(node, newNode) {
// Left side
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode; // If there's no left child, insert here
} else {
// recursive call (passing the left subtree)
this.insertNode(node.left, newNode); // Keep looking left
}
}
// Right side
else {
if (node.right === null) {
node.right = newNode; // If there's no right child, insert here
} else {
// recursive call (passing the right subtree)
this.insertNode(node.right, newNode); // Keep looking right
}
}
}
}
```

#### 🕹 Time to Play:

**Explanation Time!**: Take a look at the`insert()`

method. Why do we check if`this.root`

is`null`

?Try adding a few nodes like so:

```
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
```

🎯 Task:Can you picture the structure of the tree in your mind after adding these nodes? (draw it!). Solution here 👇

```
// Solution: the BST structure after insertion
10
/ \
5 15
/
3
```

### Step 4: Searching in the BST 🔍

Inserting is fun, but **how do we search** for a value in this tree (easy-peasy lol) ? Let’s create a method that will help us **find any value** in the BST.

```
search(value) {
return this.searchNode(this.root, value);
}
searchNode(node, value) {
if (node === null) {
return false; // Reached a leaf, value not found
}
if (value < node.value) {
return this.searchNode(node.left, value); // Search the left subtree
} else if (value > node.value) {
return this.searchNode(node.right, value); // Search the right subtree
} else {
return true; // Found the value!
}
}
```

I’ve used two functions here to keep code clean, having one function is fine also!

#### 🕹 Let’s Test It:

Try adding this search feature to your

`BinarySearchTree`

class.Use the following commands to test:

```
bst.search(5); // true
bst.search(20); // false
```

💡 Insight:Why does searching work so efficiently in a BST? (think about it first, the solution is bellow 👇)

💡 Searching in a BST is efficient because the tree is structured in a way that cuts the search space in half at each step. Since nodes on the left are smaller and nodes on the right are larger, you can quickly eliminate half of the tree depending on whether the target value is smaller or greater than the current node. This makes the search process O(log n) in the best case for a balanced tree, which is much faster than a linear search!

### Step 4: Deleting Nodes 🗑️

Now, let’s get to something a little more challenging: **deleting nodes**. Deletion in a BST can be tricky because there are **three possible cases**:

The node to be deleted is a

**leaf node**(no children).The node has

**one child**.The node has

**two children**.

** 🧠Let’s Break Down Deletion in a Binary Search Tree:**

Before diving into the code, let's discuss the **theoretical steps** for each deletion case in a Binary Search Tree. Understanding the logic behind each scenario will make it much easier when we start coding!

⚠️ Reminder: Hold off on jumping straight into the code! Take your time to fully understand the theory first. Repeat the concepts until you can visualize the operations in your mind with ease.

1. **Case 1: The Node to be Deleted is a Leaf (No Children)**

**Scenario**: The node doesn’t have any left or right children.**Action**: Since it's a leaf, it's simply removed by setting the parent’s reference to this node as`null`

.

**Example**: If you want to delete the node with value `7`

, and it’s a leaf node:

```
5
/ \
3 8
/
7 <-- Delete this
```

**Result**: The`7`

node is simply removed from the tree, and the tree is still valid.

```
5
/ \
3 8
```

2. **Case 2: The Node has One Child**

**Scenario**: The node to be deleted has either a left or right child, but not both.**Action**: In this case, the node is replaced by its only child. The parent of the node being deleted will now point to this child.

**Example**: Let’s delete node `15`

, which has only a right child (`20`

):

```
10
/ \
5 15
\
20 <-- Replace `15` with `20`
```

**Result**: The node`15`

is removed, and`20`

takes its place.

```
10
/ \
5 20
```

3. **Case 3: The Node has Two Children**

**Scenario**: The node to be deleted has both left and right children.**Action**: This is the trickiest case. Here’s what we do:Find the

**in-order successor**(smallest node in the right subtree) or**in-order predecessor**(largest node in the left subtree).Replace the value of the node to be deleted with the in-order successor or predecessor.

Finally, delete the successor or predecessor (which will be easier to delete because it will have at most one child).

**Example**: Delete node `10`

, which has two children (`5`

and `15`

):

```
10
/ \
5 15
/ \
12 20
```

**Action**: Find the in-order successor (smallest value in the right subtree), which is`12`

. Replace`10`

with`12`

, and then remove`12`

from its original position:

```
12
/ \
5 15
\
20
```

**Result**: The node`10`

is replaced by`12`

, and the tree structure remains valid.

** 👨💻Let’s Code it Now!**

Here’s the logic in action:

```
remove(value) {
this.root = this.removeNode(this.root, value);
}
removeNode(node, value) {
if (node === null) {
return null;
}
// looking for the node in the left subtree
if (value < node.value) {
node.left = this.removeNode(node.left, value);
return node;
}
// looking for the node in the right subtree
else if (value > node.value) {
node.right = this.removeNode(node.right, value);
return node;
}
// Node to be removed is found
else {
// Case 1: Node has no children
if (node.left === null && node.right === null) {
node = null;
return node;
}
// Case 2: Node has only one child
if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
// Case 3: Node has two children
let minNode = this.findMinNode(node.right);
node.value = minNode.value;
node.right = this.removeNode(node.right, minNode.value);
return node;
}
}
// Helper function to find the minimum value node in a subtree
findMinNode(node) {
if (node.left === null) {
return node;
} else {
return this.findMinNode(node.left);
}
}
```

#### 🕹 Try it Out!

Add the

`remove`

and`findMinNode`

methods to your`BinarySearchTree`

.Try removing nodes with different cases:

```
bst.remove(3); // Leaf node
bst.remove(15); // Node with one child
bst.remove(10); // Node with two children
```

🤔 Question: What happens when you delete the root node? (Answer👇)

💡 Answer:

When you delete the root node, the process depends on how many children the root has:

**No children**: If the root is a leaf, it's simply removed, and the tree becomes empty.**One child**: The root is replaced by its single child, and that child becomes the new root.**Two children**: The root is replaced by either its**in-order successor**(smallest node in the right subtree) or**in-order predecessor**(largest node in the left subtree), keeping the tree structure intact.

So, deleting the root follows the same rules as deleting any other node—it just needs special care because the root holds the entire tree together!

### 🎉 Congratulations! You’ve built a BST from Scratch!

You’ve done it! You’ve built a fully functioning **Binary Search Tree** in JavaScript. Now, let's wrap it up:

You know how to

**insert**nodes.You can

**search**for values.You can

**delete**nodes (even the tricky ones!).

### 🔮 What's Coming Next?

Our BST journey doesn’t stop here. In **Part 3**, we’ll dive into the fascinating world of **BST Traversal Algorithms**. You’ll learn how to walk through the tree in different ways, including **in-order**, **pre-order**, and **post-order**. It’s like a tree treasure hunt, but with code! 🕵️♀️🌲

And in **Part 4**, things get even more exciting as we dig deeper into **balancing** and **self-balancing trees**. Ever wondered how to keep your tree lean and efficient? We’ll explore algorithms like **AVL Trees** and **Red-Black Trees** that keep your BST from getting too wild and unruly! 🧘♂️⚖️

Stay tuned—it’s going to be a fun and enlightening ride! 🚀

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!