Back to: Python Data Structure and Algorithims

Understanding Binary Search Trees (BSTs)

In the last lesson, we explored binary trees, where each node can have at most two children.
Now, let’s take it a step further and understand Binary Search Trees (BSTs) — a special type of binary tree with a specific ordering property.

---

🔑 What Makes a Binary Tree a BST?

A Binary Search Tree (BST) is a binary tree with the following rule:

• Left child < Parent node

• Right child > Parent node

This property holds for every node in the tree, not just the root.

---

🌱 Building a BST Step by Step

Let’s add nodes to a BST one by one and see how they are positioned.

Step 1: Start with the Root

We create a BST with a single node:

This is our root.

---

Step 2: Add a Node Greater Than Root

Next, we want to add 76:

• Compare 76 with 47 (root)

• 76 > 47, so it goes to the right of 47

47
\
76

---

Step 3: Add Another Node

Now, let’s add 52:

1. Compare with root 47 → 52 > 47 → go right

2. Compare with 76 → 52 < 76 → go left

---

Step 4: Add a Smaller Node

Add 21:

• Compare with 47 → 21 < 47 → go left

---

Step 5: Add More Nodes

• Add 82 → 82 > 47, 82 > 76 → goes right of 76

• Add 18 → 18 < 47, 18 < 21 → goes left of 21

• Add 27 → 27 < 47, 27 > 21 → goes right of 21

Final BST:

---

🧠 Key Points About BSTs

1. Ordering Property:

   • All nodes in the left subtree are smaller than the parent.

   • All nodes in the right subtree are greater than the parent.

2. Efficient Searching:

   • You always know whether to go left or right.

   • This makes searching faster than a regular binary tree.

3. Recursive Nature:

   • The BST property applies to every node, not just the root.

   • Every subtree is itself a BST.

---

💡 Why BSTs Are Useful

• Fast search: O(log n) on average for balanced trees

• Efficient insertions and deletions

• Used in databases, dictionaries, and priority-based structures

---

🧩 Summary Table

---

BSTs are the foundation for many advanced data structures like AVL Trees, Red-Black Trees, and Heaps.
Mastering BSTs will make algorithms like searching, sorting, and balanced tree operations much easier.