Binary Search Trees (BST)

In the previous lesson, we learned about binary trees and different ways to traverse them.

Now we move to a very important and practical variation of binary trees called the Binary Search Tree (BST).

BSTs combine the hierarchical structure of trees with efficient searching capabilities. They are widely used in databases, operating systems, and real-time systems.

What Is a Binary Search Tree?

A Binary Search Tree is a binary tree that follows a special ordering rule.

For every node in a BST:

• All values in the left subtree are smaller
• All values in the right subtree are larger

This ordering property is what makes searching fast.

Why BSTs Are Powerful

In a normal binary tree, finding a value may require scanning every node.

In a BST, each comparison eliminates half of the remaining tree, similar to binary search on arrays.

That is why BSTs are considered logarithmic search structures.

BST Property (Very Important)

The BST property must be maintained at all times.

If even one node violates the rule, the tree is no longer a valid BST.

Many interview problems are designed to test whether you understand this property deeply.

Example of a BST

Consider the following values inserted in order:

50, 30, 70, 20, 40, 60, 80

The resulting BST will look like:

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

Searching in a BST

Searching in a BST follows the ordering rule.

If the value is smaller than the current node, move left.

If the value is larger, move right.

This continues until the value is found or the tree ends.

def search_bst(root, key):
    if root is None or root.value == key:
        return root

    if key < root.value:
        return search_bst(root.left, key)
    else:
        return search_bst(root.right, key)

Insertion in a BST

Insertion also follows the same rule as searching.

We start from the root and find the correct position where the new value should be placed.

def insert_bst(root, key):
    if root is None:
        return Node(key)

    if key < root.value:
        root.left = insert_bst(root.left, key)
    elif key > root.value:
        root.right = insert_bst(root.right, key)

    return root

Why Inorder Traversal Matters in BST

One unique and powerful feature of BSTs is:

Inorder traversal of a BST always produces sorted output.

This property is heavily used in sorting and data indexing.

Time Complexity

The time complexity depends on the height of the tree.

In the best case (balanced BST):

O(log n)

In the worst case (skewed tree):

O(n)

This worst case happens when values are inserted in sorted order.

Real-World Applications

Binary Search Trees are used in:

• Database indexing
• File system directory structures
• Symbol tables
• Auto-complete systems

Limitations of BST

A simple BST does not balance itself.

If inserted values are already sorted, the tree becomes a linked list.

This is why balanced trees like AVL and Red-Black Trees exist.

Exercises

Quick Quiz

In the next lesson, we will study AVL Trees, which solve the imbalance problem of standard BSTs and guarantee logarithmic performance.