# 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 subtreeare smaller, and values in theright subtreeare 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:

**Value (Key):**This is the knight’s name, or in our case, a number.**Left Child:**The knight guarding the left side of the battlefield (lower value).**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:

Start at the root (top node). Is the value you’re looking for

**6**? No, it’s**8**.Is

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

**6**equal to**3**? Nope. But**6**is greater than**3**, so we go to the right child, which is**6**.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.

Start at the root:

**5**is less than**8**, so move left to**3**.Now,

**5**is greater than**3**, so move right to**6**.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!

**Faster Searching:**With the BST’s ordered structure, you eliminate half of the possibilities at each step, making searching super efficient (logarithmic time).**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.**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!