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

Introduction

In computer science, a Binary Search Tree (BST) is a binary tree that stores keys in an ordered manner, allowing fast lookup, insertion, and deletion of nodes while maintaining a dynamic set of elements.

Definition and Structure

A BST node contains a key, optional satellite data, and three pointers: left, right, and parent. A nil pointer denotes the absence of a child or parent. The root is the unique node whose parent is nil.

Key Properties

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

If a node has a 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.

Tree Traversals

BSTs support three depth‑first traversals:

Preorder (root, left, right)

Inorder (left, root, right) – yields keys in sorted order

Postorder (left, right, root)

Inorder traversal pseudocode:

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

Search Operation

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 children until nil:

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

Finding the largest key follows right children analogously:

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

Successor and Predecessor

The successor of a node x (the smallest key greater than x.key) is found as follows:

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

Two cases are illustrated with diagrams in the original article (omitted here for brevity).

Insertion

Insertion maintains BST order by locating the appropriate leaf position and attaching the new node z:

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 is handled in 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 the right subtree). This may require a transplant of y 's right child before the final replacement.

Helper procedure TRANSPLANT replaces one subtree with another:

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

Full deletion algorithm:

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 roughly halves the remaining search space, the average time for search, insertion, and deletion is O(log n). In the worst case (a degenerate tree), operations degrade to O(n). Balanced variants such as AVL, Red‑Black, and Splay trees keep height logarithmic.

References

Introduction to Algorithms (CLRS)

Wikipedia – Binary Search Tree

Visualgo – BST visualizations