Binary Search Trees

Binary Search Trees (BST)

In previous tutorials, we learned about basic Binary Trees. A regular Binary Tree can hold data in any random order.

However, if we want to find a specific item in a random tree, we have to search every single node. This is slow!

To fix this, Computer Scientists created the Binary Search Tree.

1. The Rules of a BST

A Binary Search Tree is just a normal Binary Tree that strictly follows one golden rule.

For every single node in the tree:

• All values in its Left Subtree must be smaller than the node's value.
• All values in its Right Subtree must be larger than the node's value.
• (Usually, duplicate values are not allowed, or they are strictly placed on one specific side).

Binary Search Tree: Left is always smaller, Right is always larger.

2. Why are BSTs so fast?

A BST works exactly like the Binary Search algorithm we learned for Arrays.

Imagine you are looking for the number 60 in the tree above.

1. You start at the Root: 50.
2. Is 60 greater than or less than 50? It is greater!
3. You instantly ignore the entire left half of the tree. You move Right to 70.
4. Is 60 greater than or less than 70? It is less!
5. You move Left and find 60!

With just two comparisons, we eliminated over half of the tree. This gives searching a blistering O(log n) time complexity!

3. BST Operations: Insertion

How do we build a Binary Search Tree? We insert nodes one by one, letting them "fall" into their correct places.

Let's insert 45 into the tree above:

1. Start at 50. 45 is less than 50, so go Left.
2. We are at 30. 45 is greater than 30, so go Right.
3. We are at 40. 45 is greater than 40, so go Right.
4. There is no node to the right of 40! We create a new node for 45 here.

4. BST Operations: Deletion

Deleting a node is the hardest operation in a BST because we have to keep the tree connected and sorted.

There are 3 specific cases for deletion:

Case 1: The node is a Leaf (No Children)

This is easy! If you want to delete 20, you just remove it. The tree remains perfectly valid.

Case 2: The node has exactly ONE Child

If you want to delete 70 (assuming it only had 60 as a child), you just delete 70 and connect its parent (50) directly to its child (60).

Case 3: The node has TWO Children

If you want to delete the Root (50), you can't just delete it, or the whole tree splits in half! Instead, you find its In-Order Successor.

• The In-Order Successor is the smallest value in the Right subtree.
• You copy the Successor's value into the Root, and then delete the Successor.

5. Coding a BST (Python)

Let's look at how to implement the Node structure, Insert method, and Search method in Python.

# 1. Create the TreeNode Class
class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

# 2. Insert Function
def insert(root, key):
    # If tree is empty, return a new node
    if root is None:
        return TreeNode(key)
    # Otherwise, recurse down the tree
    if key < root.val:
        root.left = insert(root.left, key)
    elif key > root.val:
        root.right = insert(root.right, key)
    # Return the (unchanged) node pointer
    return root
# 3. Search Function
def search(root, key):
    # Base Cases: root is null or key is present at root
    if root is None or root.val == key:
        return root
    # Key is greater than root's key, search Right
    if root.val < key:
        return search(root.right, key)
    # Key is smaller than root's key, search Left
    return search(root.left, key)
# Let's test it out!
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 20)
insert(root, 40)
insert(root, 70)
insert(root, 60)
insert(root, 80)
# Search for a value
result = search(root, 60)
if result:
    print("Found:", result.val)
else:
    print("Value not found in BST.")

6. Time and Space Complexity

• Time Complexity (Average): O(log n). Because we eliminate half of the tree with every step, searching, inserting, and deleting are exceptionally fast.
• Time Complexity (Worst Case): O(n). If you insert data that is already sorted (e.g., 10, 20, 30, 40), the tree just forms a straight line! It basically degrades into a slow Linked List.
• Space Complexity: O(n) to hold the nodes, plus O(h) for the recursive call stack (where h is the tree's height).