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!

Mnt Code

Sep 28, 2024

Article voiceover

1×

0:00

-0:31

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):

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:

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!

Mnt Code Blog

Discussion about this post