DSA Binary Search Trees

A binary search tree, or BST, is a tree where every node holds one value and has at most two children. The tree follows one strict rule that keeps the data organized and makes searching fast.

Think of a game where you guess a number between 1 and 100. A friend says "higher" or "lower" after each guess. Every answer removes half of the remaining options. A BST gives a program the same power over stored data.

The BST Rule

• Every value in the left subtree is smaller than the node.
• Every value in the right subtree is larger than the node.
• Both subtrees follow the same rule.

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

Every number left of 50 is below 50, and every number right of 50 is above 50. Node 30 follows the same rule for its own children.

Building the Node

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Inserting a Value

Start at the root. Move left when the new value is smaller and right when it is larger. Place the new node at the first empty spot.

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root

root = None
for number in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, number)

Insert 65 into the tree above

65 vs 50 -> go right
65 vs 70 -> go left
65 vs 60 -> go right
Empty spot found, place 65 as the right child of 60

Searching for a Value

Searching follows the same left-or-right path as insertion.

def search(root, target):
    if root is None:
        return False
    if target == root.value:
        return True
    if target < root.value:
        return search(root.left, target)
    return search(root.right, target)

print(search(root, 60))   # True
print(search(root, 99))   # False

Each step discards an entire subtree. A balanced tree with 1,000,000 nodes needs only about 20 steps.

Inorder Traversal Gives Sorted Order

Visiting the left subtree, the node itself, and the right subtree in that order prints values from smallest to largest.

def inorder(root):
    if root:
        inorder(root.left)
        print(root.value, end=" ")
        inorder(root.right)

inorder(root)   # 20 30 40 50 60 70 80

This property makes a BST a natural way to keep sorted data.

Deleting a Node

Deletion has three cases.

Case 1: A Leaf Node

Remove the node. Nothing else changes.

Case 2: One Child

Replace the node with its only child.

Case 3: Two Children

Find the inorder successor, which is the smallest value in the right subtree. Copy that value into the node, and delete the successor from the right subtree.

def smallest(node):
    while node.left:
        node = node.left
    return node

def delete(root, value):
    if root is None:
        return None
    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        successor = smallest(root.right)
        root.value = successor.value
        root.right = delete(root.right, successor.value)
    return root

The Balance Problem

Inserting sorted numbers such as 10, 20, 30, 40 builds a tree that leans to one side.

10
  \
   20
     \
      30
        \
         40

This tree behaves like a linked list, and every search takes O(n) time. Self-balancing trees such as AVL trees and red-black trees fix the lean automatically.

Complexity Summary

• Search, insert, delete (balanced): O(log n)
• Search, insert, delete (skewed): O(n)
• Space: O(n) to store the nodes

Real-Life Uses

Databases build tree-based indexes so a lookup skips most of the stored records. Autocomplete features keep sorted word lists for quick range searches. Language libraries use balanced trees inside ordered maps and sets. A contact app can keep names sorted so every new entry lands in the correct spot instantly.

Common Mistakes

Many learners compare only a node with its direct children and miss the rule for the whole subtree. Every value on the left side must stay below the node, even deep inside the branch. Duplicate values need a clear policy, such as ignoring repeats or keeping a count in each node. Draw the tree after every insert to catch rule violations early.

Key Points

• A BST keeps smaller values on the left and larger values on the right.
• Insert and search follow one path from the root downward.
• Inorder traversal returns values in sorted order.
• Deleting a node with two children uses the inorder successor.
• A skewed tree loses its speed advantage.
• Balanced variants keep operations at O(log n).