Binary Search Trees — Data Structures

Posted on by

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

  1. Inorder Traversal (Left → Root → Right)
    Gives elements in sorted order!
    Example output for our tree: 20, 30, 40, 50, 60, 70, 80
  2. Preorder Traversal (Root → Left → Right)
    Useful for creating a copy of the tree.
  3. 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

ConceptDescription
DefinitionA binary tree where left < root < right
PurposeFast searching, inserting, and deleting
RuleLeft child smaller, right child larger
Traversal (Inorder)Gives sorted elements
ApplicationsDatabases, searching, indexing, symbol tables