Binary Search Tree in Data Structures

A Binary Search Tree (BST) is a node‑based binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

This ordering property enables efficient search, insertion, and deletion operations in O(log n) average time, provided the tree remains balanced.

BST Node Structure

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

Basic Operations

Search

Start from the root and compare the target key with the current node's key. If equal, found; if smaller, go left; if larger, go right.

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

Insert

Insert a new key in the appropriate position using the same logic as search. If the key already exists, we typically do not insert duplicates.

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

Delete

Deletion is more involved. There are three cases:

• Node has no children: simply remove it.
• Node has one child: replace the node with its child.
• Node has two children: find the in‑order successor (smallest in the right subtree) or in‑order predecessor (largest in the left subtree), copy its value to the current node, and recursively delete that successor/predecessor.

def min_value_node(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def delete(root, key):
    if root is None:
        return root
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        # node with only one child or no child
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        # node with two children
        temp = min_value_node(root.right)
        root.key = temp.key
        root.right = delete(root.right, temp.key)
    return root

Complexity

For balanced BSTs (e.g., AVL or Red‑Black trees), the worst‑case time is guaranteed O(log n).

Advantages & Disadvantages

Advantages

• Fast search, insert, and delete on average.
• In‑order traversal gives sorted order without extra cost.
• More flexible than arrays or linked lists for dynamic data.

Disadvantages

• Can become skewed (degenerate) if keys are inserted in sorted order, leading to O(n) performance.
• No direct access by index (unlike arrays).
• More complex to implement than simpler structures like heaps.

Applications

• Database indexing and in‑memory sorted data storage.
• Implementation of associative arrays (maps/dictionaries) and sets.
• Routing tables in network routers.
• Self‑balancing BST variants (AVL, Red‑Black) are used in many language libraries (e.g., std::map in C++, TreeMap in Java).