Binary Search Trees — Data Structures -

🌱 What Is a Binary Search Tree?

A Binary Search Tree, or BST, is a special type of binary tree that keeps its elements in a sorted order.
This makes searching, inserting, and deleting data very fast — much faster than in an unsorted tree or a list.

But what makes it special?

It follows a simple rule at every node:

👉 Left child < Parent < Right child

That means:

Every value in the left subtree is smaller than the node’s value.
Every value in the right subtree is larger than the node’s value.

🌳 Let’s Look at an Example

Imagine this Binary Search Tree:

        50
       /  \
     30    70
    / \    / \
  20  40  60  80

Here’s how it follows the BST rule:

The root node is 50.
Everything left of 50 (30, 20, 40) is smaller than 50.
Everything right of 50 (70, 60, 80) is greater than 50.
If you pick 30, its left child 20 is smaller, and its right child 40 is larger.
The same goes for 70 — its left child 60 < 70, and its right child 80 > 70.

It’s like a perfectly balanced see-saw of numbers!

🌿 Why Is It Called a “Search” Tree?

Because it makes searching lightning fast ⚡

Let’s say you want to find 40 in the above tree.

Start at the root (50).
Since 40 < 50, go left.
Now you’re at 30.
Since 40 > 30, go right.
You find 40! 🎯

You didn’t need to look through every element — just followed the logical path.
This is much faster than searching line by line through an unsorted list.

🌸 Everyday Analogy

Think of it like searching a word in a dictionary:
You don’t start from the first page every time.
If you’re looking for “Mango,” you flip somewhere around the middle — maybe near “L.”
Then, if “Mango” is further ahead, you go right. If it’s before “L,” you go left.

That’s exactly how a Binary Search Tree behaves — divide and conquer!

🌺 Basic Operations in a BST

Let’s quickly go over what we can do with a BST:

1. Search

Start from the root.
Compare the value you’re looking for with the current node.
Move left if it’s smaller, or right if it’s larger.
Continue until you find it or reach a NULL (meaning it doesn’t exist).

2. Insertion

Start at the root.
Compare the new value with the current node.
Go left if it’s smaller, right if it’s larger.
Place the new node when you find an empty spot.

Example:
Insert 65 in our tree:

        50
       /  \
     30    70
    / \    / \
  20  40  60  80
           \
            65

Since 65 > 60 but < 70, it fits as the right child of 60.

3. Deletion

There are three possible cases when deleting a node:

The node is a leaf (no children) → just remove it.
The node has one child → replace it with its child.
The node has two children → replace it with its inorder successor (the smallest value in the right subtree).

Deletion keeps the BST rules intact.

🌻 Traversing a BST

Tree traversal means visiting every node in some order.
The three common methods are:

Inorder Traversal (Left → Root → Right)
Gives elements in sorted order!
Example output for our tree: 20, 30, 40, 50, 60, 70, 80
Preorder Traversal (Root → Left → Right)
Useful for creating a copy of the tree.
Postorder Traversal (Left → Right → Root)
Useful for deleting or freeing nodes.

🌼 Diagram – Binary Search Tree Structure

           50
         /    \
       30      70
      / \      / \
    20  40   60  80

Left subtree (30, 20, 40) < 50
Right subtree (70, 60, 80) > 50
That’s the core rule of a BST.

🌻 Advantages of BST

✅ Fast Searching – Average time complexity is O(log n)
✅ Efficient Insertion/Deletion – Keeps data sorted automatically
✅ Easy to Traverse – Especially for sorted output using inorder traversal
✅ Dynamic Size – Can grow or shrink as needed (unlike arrays)

🌸 A Word of Caution

BSTs work best when they’re balanced.
If you keep inserting values in increasing order (like 10, 20, 30, 40…),
the tree will lean to one side — becoming more like a linked list.
This makes it slower (O(n) time).

To fix this, we use balanced BSTs like:

AVL Trees
Red-Black Trees

But that’s a story for another day. 🌱

🌷 Summary

Concept	Description
Definition	A binary tree where left < root < right
Purpose	Fast searching, inserting, and deleting
Rule	Left child smaller, right child larger
Traversal (Inorder)	Gives sorted elements
Applications	Databases, searching, indexing, symbol tables