C++UCS301
Trees & ApplicationsC++17

Binary Search Tree

A BST maintains smaller keys in the left subtree and larger keys in the right subtree, enabling ordered operations.

Open this in the visual lab

What to understand

  • Search and insertion
  • Three deletion cases
  • Successor and predecessor
  • Shape dependence

Remember this

  1. 1Operations cost O(h)
  2. 2Balanced gives O(log n)
  3. 3Sorted insertion can create a chain
  4. 4Define a duplicate-key policy

Detailed notes

The BST invariant is global: every key in a node's left subtree precedes the node, and every key in the right subtree follows it. Local child comparisons alone are not enough to validate an entire tree.

Deletion has three structural cases. A leaf disappears, a one-child node is replaced by its child, and a two-child node exchanges logical content with its inorder successor or predecessor before reducing to an easier case.

How it works

  1. 1Follow one branch per comparison for search and insertion.
  2. 2Define a consistent duplicate policy.
  3. 3For two-child deletion, locate successor or predecessor.
  4. 4Return updated subtree roots so parent links remain correct.

Worked trace

Delete a node with two children

Delete 50; right subtree minimum is 60
  1. 1Locate key 50 by BST comparisons.
  2. 2Both children exist, so find inorder successor 60.
  3. 3Copy or move successor key 60 into the logical position of 50.
  4. 4Delete the original successor node, which has at most one child.
Result: BST ordering is preserved and the problem reduces to an easier deletion case

Where it is used

  • Ordered sets and maps
  • Range queries and sorted iteration
  • Symbol tables when order matters

Common mistakes

  • Validating only parent-child order
  • Losing a subtree during deletion
  • Assuming arbitrary insertion keeps height logarithmic

Complexity analysis

OperationBestAverageWorstExtra space
SearchO(log n)O(log n)O(n)O(1)
InsertO(log n)O(log n)O(n)O(1)
DeleteO(log n)O(log n)O(n)O(1)

C++ implementation

C++17 reference
main.cpp

BST insertion, search, and deletion

Deletion replaces a two-child node with its inorder successor, then removes that successor.

struct Node { int key; Node* left; Node* right; };

Node* insert(Node* root, int key) {
    if (!root) return new Node{key, nullptr, nullptr};
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;
}

bool contains(Node* root, int key) {
    while (root && root->key != key)
        root = key < root->key ? root->left : root->right;
    return root != nullptr;
}

Node* erase(Node* root, int key) {
    if (!root) return nullptr;
    if (key < root->key) root->left = erase(root->left, key);
    else if (key > root->key) root->right = erase(root->right, key);
    else {
        if (!root->left || !root->right) {
            Node* child = root->left ? root->left : root->right;
            delete root;
            return child;
        }
        Node* successor = root->right;
        while (successor->left) successor = successor->left;
        root->key = successor->key;
        root->right = erase(root->right, successor->key);
    }
    return root;
}
32 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.