Binary Search Tree (BST)

What is a binary search tree?

A tree is a structure of nodes connected like a family tree: one root at the top, and each node can have children. In a binary tree every node has at most two children, called left and right.

A binary search tree (BST) adds one rule that makes it powerful:

For every node: all values in its left subtree are smaller, and all values in its right subtree are bigger.

Analogy: guessing a number between 1 and 100. You ask “is it bigger than 50?” — and with one question you throw away half the possibilities. A BST bakes those questions into its shape.

Words you need

Term	Meaning
Root	The top node (no parent)
Leaf	A node with no children
Subtree	A node together with all its descendants
Depth of a node	How many edges it is below the root
Height of the tree	The number of levels (the longest root-to-leaf path)

Searching

Start at the root and compare:

• target == node → found!
• target < node → go left.
• target > node → go right.
• reached an empty spot (NULL) → the value is not in the tree.

Every comparison goes one level down, so the work equals the height h of the tree: O(h). For a nicely balanced tree with n nodes, h ≈ log₂ n — about 20 steps for a million nodes!

Inserting

Insertion is a search that fails: walk down exactly as if you were searching for the new value, and when you reach the empty spot, put the new node there. New nodes are always added as leaves.

Deleting — three cases

1. The node is a leaf → just remove it.
2. The node has one child → connect its parent directly to that child (the whole subtree moves up).
3. The node has two children → find its in-order successor: go right once, then left as far as possible. That is the smallest value bigger than the node. Copy that value into the node, then delete the successor (which has at most one child, so it is case 1 or 2).

The 3D model walks through all three. Try deleting the root of the starting tree to see case 3.

Traversals

A traversal visits every node once. The four common orders:

Traversal	Order	Use
In-order	Left, Node, Right	Gives a BST’s values in sorted order
Pre-order	Node, Left, Right	Copying / saving a tree
Post-order	Left, Right, Node	Deleting a tree (children before parent)
Level-order	Level by level, using a queue	Shortest paths, printing by level (this is BFS)

Code

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

def insert(node, x):
    if node is None:
        return Node(x)
    if x < node.value:
        node.left = insert(node.left, x)
    elif x > node.value:
        node.right = insert(node.right, x)
    return node                      # duplicates are ignored

def search(node, x):
    while node is not None and node.value != x:
        node = node.left if x < node.value else node.right
    return node                      # None if not found

def delete(node, x):
    if node is None:
        return None
    if x < node.value:
        node.left = delete(node.left, x)
    elif x > node.value:
        node.right = delete(node.right, x)
    else:
        if node.left is None:        # case 1 or 2
            return node.right
        if node.right is None:       # case 2
            return node.left
        succ = node.right            # case 3: in-order successor
        while succ.left:
            succ = succ.left
        node.value = succ.value
        node.right = delete(node.right, succ.value)
    return node

def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.value)
        inorder(node.right, out)
    return out

root = None
for v in [50, 30, 70, 20, 40, 60, 80, 35]:
    root = insert(root, v)
print(inorder(root, []))   # [20, 30, 35, 40, 50, 60, 70, 80]
root = delete(root, 50)
print(inorder(root, []))   # [20, 30, 35, 40, 60, 70, 80]

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node *left = nullptr, *right = nullptr;
    Node(int v) : value(v) {}
};

Node* insert(Node* node, int x) {
    if (!node) return new Node(x);
    if (x < node->value) node->left = insert(node->left, x);
    else if (x > node->value) node->right = insert(node->right, x);
    return node;
}

Node* remove(Node* node, int x) {
    if (!node) return nullptr;
    if (x < node->value) node->left = remove(node->left, x);
    else if (x > node->value) node->right = remove(node->right, x);
    else {
        if (!node->left)  { Node* r = node->right; delete node; return r; }
        if (!node->right) { Node* l = node->left;  delete node; return l; }
        Node* succ = node->right;
        while (succ->left) succ = succ->left;
        node->value = succ->value;
        node->right = remove(node->right, succ->value);
    }
    return node;
}

void inorder(Node* node) {
    if (!node) return;
    inorder(node->left);
    cout << node->value << " ";
    inorder(node->right);
}

int main() {
    Node* root = nullptr;
    for (int v : {50, 30, 70, 20, 40, 60, 80, 35}) root = insert(root, v);
    inorder(root);   // 20 30 35 40 50 60 70 80
}

The weakness: unbalanced trees

The speed of a BST depends entirely on its shape. Insert 10, 20, 30, 40, 50 in order and every node goes right — the tree becomes a straight line (a skewed tree) and search becomes O(n), no better than a linked list.

Self-balancing trees such as AVL trees and Red-Black trees fix this by rotating nodes after insertions and deletions to keep the height about log₂ n. std::map in C++ and TreeMap in Java are Red-Black trees.

Where are BSTs used?

• Ordered maps and sets (std::map, std::set, TreeMap).
• Database indexes (as their bigger cousins, B-trees and B+ trees).
• Auto-complete and range queries such as “all students with marks between 60 and 80”.

Common mistakes

• Checking only a node’s direct children. The BST rule applies to the whole subtree.
• Forgetting to return / re-link the new subtree root after a recursive insert or delete.
• Assuming O(log n) without a balanced tree.