Skip to content
Deadline to Die

Module 2: Binary Search Trees (The Smart Sorter)

📚 Module 2: Binary Search Trees (BST)

Course ID: DSA-302
Subject: The Smart Sorter

A Binary Search Tree (BST) is a binary tree with a special rule. This rule makes searching for data incredibly fast.

🏗️ Step 1: The BST Rule

For Every node in the tree:

  1. All data on the Left side must be Smaller than the node.
  2. All data on the Right side must be Larger than the node.

🧩 The Analogy: The Guessing Game

Imagine you are looking for number 42 in a BST.

  • You start at the Root (50).
  • 42 is smaller than 50? Go Left.
  • Now you are at a new node (30).
  • 42 is larger than 30? Go Right.
  • Result: In just two steps, you found the number! (O(log n) Search).

🏗️ Step 2: The Complexity Advantage

  • Array Search: O(n) - You look at everything.
  • BST Search: O(log n) - You discard 50% of the work at every step.

📊 The Scale:

  • 1,000,000 items in an array? 1,000,000 steps.
  • 1,000,000 items in a BST? ~20 steps.

🏗️ Step 3: The “Unbalanced” Danger

If you add numbers in order (1, 2, 3, 4, 5) to a BST, it becomes a single straight line.

  • The Problem: It’s no longer a tree; it’s just a slow Linked List! (O(n)).
  • Senior Solution: We use “Self-Balancing” trees like AVL or Red-Black trees to keep the branches even.

🥅 Module 2 Review

  1. BST Rule: Left < Root < Right.
  2. Efficiency: Logarithmic speed for search and insert.
  3. Balance: The importance of keeping branches even.

:::tip Senior Tip Most modern databases use a variation of the BST called a B-Tree to store their indexes. Every time you run a SQL WHERE id = 5 query, you are using tree logic! ::: Riverside. Riverside.