Master Binary Search Trees: Definitions, Traversals, and Core Operations

Definition

A Binary Search Tree (BST) is a binary tree where each node stores a key, optional satellite data, and pointers to its left child, right child, and parent. A nil pointer represents the absence of a child or parent. The root is the only node whose parent is nil.

Properties

BSTs satisfy three key properties:

If a node has a non‑empty left subtree, every key in that subtree is less than or equal to the node’s key.

If a node has a non‑empty right subtree, every key in that subtree is greater than or equal to the node’s key.

Both left and right subtrees of any node are themselves BSTs.

These properties hold recursively for every node in the tree.

Traversal

BSTs can be traversed using preorder, inorder, or postorder walks. Inorder traversal yields keys in sorted order. The pseudocode for inorder walk is:

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

Applying this to the example tree produces the sequence 2, 4, 5, 6, 7, 8.

Search

The recursive search operation 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)

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

Minimum and Maximum

Finding the smallest key follows left pointers until nil; the largest key follows right pointers.

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

Similarly, the maximum is obtained by traversing right children:

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

Successor and Predecessor

The successor of a node x is the smallest key greater than x.key. If x 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

Illustrations show finding the successor of 68 (right‑subtree minimum) and of 17 (first left‑turn ancestor).

Insertion

Insertion maintains BST properties by locating the appropriate nil leaf 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 z has no children – simply remove it.

Node z has one child – replace z with its child.

Node z has two children – replace z with its successor y (the minimum of z’s right subtree). The algorithm uses a helper TRANSPLANT to replace subtrees.

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

Summary

Because each comparison halves the remaining search space, average‑case operations on a balanced BST run in O(log n) time, though a degenerate (linked‑list) BST degrades to O(n). Balanced variants such as AVL trees, red‑black trees, and Splay trees guarantee O(log n) height.

References

1. Cormen, Leiserson, Rivest, Stein – “Introduction to Algorithms”.

2. Wikipedia – Binary Search Tree.

3. Visualgo – BST visualizations.