Mastering Binary Search Trees: Definitions, Operations, and Pseudocode

Definition

A Binary Search Tree (BST) is a binary tree where each node stores a key, optional satellite data, and pointers left, right, and parent. The root is the only node whose parent is nil. For any node, all keys in its left subtree are ≤ the node's key, and all keys in its right subtree are ≥ the node's key.

Properties

If a node's left subtree is non‑empty, every key in that subtree is ≤ the node's key.

If a node's right subtree is non‑empty, every key in that subtree is ≥ the node's key.

Both left and right subtrees are themselves BSTs.

Tree Traversal

BSTs can be traversed using preorder, inorder, or postorder walks. Inorder traversal yields keys in ascending order. Pseudocode for inorder walk:

INORDER-TREE-WALK(x)
    if x != nil
        INORDER-TREE-WALK(x.left)
        print x.key
        INORDER-TREE-WALK(x.right)

Search

The recursive search algorithm locates a node with a given key k:

TREE-SEARCH(x, k)
    if x == nil or k == x.key
        return x
    if k < x.key
        return TREE-SEARCH(x.left, k)
    else
        return TREE-SEARCH(x.right, k)

Example: searching for key 5 starts at the root 6, moves left to 4, then right to 5, and returns the node.

Minimum and Maximum

Finding the smallest key follows left pointers from the root until nil is reached; the largest key follows right pointers similarly.

TREE-MINIMUM(x)
    while x.left != nil
        x = x.left
    return x

TREE-MAXIMUM(x)
    while x.right != nil
        x = x.right
    return x

Successor and Predecessor

The successor of a node is the smallest key greater than the node's key. If the node has a right subtree, the successor is the minimum of that subtree; otherwise, walk up the tree until encountering a node that is a left child of its parent.

TREE-SUCCESSOR(x)
    if x.right != nil
        return TREE-MINIMUM(x.right)
    y = x.p
    while y != nil and x == y.right
        x = y
        y = y.p
    return y

Examples illustrate both cases, including finding the successor of 68 (right‑subtree minimum 72) and of 17 (first left‑child ancestor).

Insertion

Insertion maintains BST properties by locating the appropriate leaf position and attaching the new node as a left or right child.

TREE-INSERT(T, z)
    y = nil
    x = T.root
    while x != nil
        y = x
        if z.key < x.key
            x = x.left
        else
            x = x.right
    z.p = y
    if y == nil
        T.root = z
    elseif z.key < y.key
        y.left = z
    else
        y.right = z

Deletion

Deletion handles three cases:

Node has no children – simply remove it.

Node has one child – replace the node with its child.

Node has two children – replace the node with its successor (the minimum of its right subtree) using the TRANSPLANT helper.

TRANSPLANT(T, u, v)
    if u.p == nil
        T.root = v
    elseif u == u.p.left
        u.p.left = v
    else
        u.p.right = v
    if v != nil
        v.p = u.p

TREE-DELETE(T, z)
    if z.left == nil
        TRANSPLANT(T, z, z.right)
    elseif z.right == nil
        TRANSPLANT(T, z, z.left)
    else
        y = TREE-MINIMUM(z.right)
        if y.p != z
            TRANSPLANT(T, y, y.right)
            y.right = z.right
            y.right.p = y
        TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y

Complexity Summary

Because each comparison discards roughly half of the remaining nodes, average‑case search, insertion, and deletion run in O(log n) time, proportional to the tree height. In the worst case (a degenerate tree), the complexity degrades to O(n). Balanced variants such as AVL trees or red‑black trees keep height at O(log n).

References

CLRS – Introduction to Algorithms

Wikipedia – Binary Search Tree

Visualgo – BST visualisation