Binary Search Trees: The Knights of Data Kingdom - Part 1

Part 8 of data structures series. This is the first in a miniseries (3-5 articles) where we'll take a deep dive into Binary Search Trees (BSTs). In this article, we’ll focus on the theory behind BST.

Hey there, brave learner! 🏰 Welcome to the magical land of Binary Search Trees (BSTs). Don’t worry, we won’t ask you to slay dragons 🐉, but by the end of this adventure, you’ll be navigating through trees like a pro 😎. Grab your sword (or keyboard), because we’re diving into one of the coolest data structures in programming. Let’s start from the beginning!

⁉️What the hell is a Binary Search Tree (BST)?

Imagine you’re the ruler of a kingdom. Your kingdom has many villages, and you need to visit them often. But instead of wandering aimlessly, you’ve decided to build roads in a very logical way so you can always find the shortest path. This well-organized system is like a Binary Search Tree!

In technical terms:

• A Binary Tree is a tree-like data structure where each node can have at most two children (left and right).

• A Binary Search Tree (BST) is a binary tree that follows a special rule:

"For each node, values in the left subtree are smaller, and values in the right subtree are greater than the node’s value."

Let’s meet the knights of your kingdom—the nodes!

🤺The Noble Nodes

Every BST is made up of nodes, and every node is like a knight on the battlefield. A node has three important things:

1. Value (Key): This is the knight’s name, or in our case, a number.

2. Left Child: The knight guarding the left side of the battlefield (lower value).

3. Right Child: The knight guarding the right side (higher value).

Quick Example:

Here’s a simple binary search tree to picture it.

        8  // root node
       / \
      3   10  //10 is the right child node of 8 (root node)
     / \    \
    1   6    14  // 1 is the left child node of 3 (left child node of 8)
       / \   /
      4   7 13  // 4, 7 and 13 are called leafs (don't have children)

• The node with value 8 is the root.

• On its left, we have 3 (because 3 < 8) and on the right, we have 10 (because 10 > 8).

• This rule applies to every other node. The left is always smaller, and the right is always larger.

🧐Why Should We Care About BSTs?

Great question! Imagine you're in a library with millions of books. If those books are randomly placed, finding one specific book could take forever. But what if the books were arranged alphabetically? That’s essentially what a BST does—it helps you search, insert, and delete items in a very efficient way.

In fact, operations like searching for a value, adding a new value, or removing an existing value can be done in O(log n) time. That’s superfast, especially when dealing with large amounts of data.

Example:

Imagine you want to find a knight (node) with a specific number, say 6.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

Here’s how the search journey works:

1. Start at the root (top node). Is the value you’re looking for 6? No, it’s 8.

2. Is 6 less than 8? Yes! So, move left to 3.

3. Is 6 equal to 3? Nope. But 6 is greater than 3, so we go to the right child, which is 6.

4. Aha! You’ve found the knight you're looking for!

This search process cuts the number of nodes to check in half each time, making it quick and efficient.

🏇Inserting a New Knight Into the Kingdom

Let’s say a new knight with the value 5 arrives, and you need to place him into your BST. The insertion follows the same “left is smaller, right is bigger” rule.

1. Start at the root: 5 is less than 8, so move left to 3.

2. Now, 5 is greater than 3, so move right to 6.

3. Finally, 5 is less than 6, so it becomes the left child of 6.

Your BST now looks like this:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      5   7 13

Easy, right? The tree grows in a way that maintains the BST structure. This helps keep search and other operations efficient.

⚔️The Noble Deletion (Or, How to Retire a Knight)

What happens when a knight (node) is ready to retire? Deleting a node can be a bit tricky because we don’t want to mess up the kingdom’s balance. There are three cases to consider:

1. If the knight (node) has No Children (Leaf Node):

If the node has no children, just remove it. Simple as that.

2. If the knight (node) has One Child:

If the node has one child, you let the child take the place of the node.

3. If the knight (node) has Two Children:

This is where things get spicy! If a node has two children, you need to find the in-order successor (the smallest value in the right subtree) or the in-order predecessor (the largest value in the left subtree) to replace it.

PS: I know deletion might seem tricky or tough to grasp at first (I’ve been there too!), but don’t worry— in the next coding chapter, we’ll break it down step-by-step and explain it in detail. So, keep going 😎.

🆚BST vs. Other Trees: Why is BST Special?

Now you might wonder why a Binary Search Tree? Why not just a regular tree, or a list, or something else? Well, it’s all about efficiency!

1. Faster Searching: With the BST’s ordered structure, you eliminate half of the possibilities at each step, making searching super efficient (logarithmic time).

2. Efficient Insertion and Deletion: Maintaining the tree’s structure allows for quick insertion and deletion, unlike a sorted array where you have to shift things around.

3. Balanced vs. Unbalanced Trees: In a perfectly balanced BST, the height of the tree is kept to a minimum, ensuring fast operations. But beware of an unbalanced tree! If nodes are inserted in sorted order, the BST can become more like a list, which is less efficient.

🌳Interactive Time: Build Your Own Tree!

Let’s play a little game (use a pen and a paper, no coding now please haha)! You are now the ruler of a kingdom, and you need to construct your own BST. Try to build it step by step using the following values in order: 15, 10, 20, 8, 12, 17, 25.

Here’s how it goes:

• Insert 15 first, which becomes the root.

• Then insert 10. It’s smaller than 15, so it goes to the left.

• Insert 20. It’s greater than 15, so it goes to the right.

• Insert 8. Smaller than both 15 and 10, so it goes left of 10.

• Keep going with the rest!

Solutions:

What does your tree look like? If you did it right, it should look something like this:

        15
       /  \
      10   20
     / \   / \
    8  12 17 25

Congratulations! You’ve just built a Binary Search Tree! 🌲✨

🏰Closing the Kingdom Gates (tired of watching it today lol)

Now you’re equipped with the knowledge of Binary Search Trees, one of the most powerful data structures in the land of algorithms. You know how to search, insert, and delete nodes while maintaining order in your kingdom.

In the next adventure, we’ll get our hands dirty by actually coding a BST from scratch! So polish your armor and sharpen your coding skills, because it’s about to get even more fun! 🛡️

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