BST Delete Operation in DSA C++ - Time & Space Complexity

Time Complexity: BST Delete Operation

O(h)

Understanding Time Complexity

We want to understand how long it takes to remove a value from a Binary Search Tree (BST).

Specifically, how the time changes as the tree grows bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

Node* deleteNode(Node* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;
        Node* temp = findMin(root->right);
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

This code removes a node with a given key from a BST, adjusting links to keep the tree valid.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls down the tree to find the node to delete.
• How many times: At most once per tree level, moving left or right.
• Additional operation: Finding the minimum node in the right subtree (also a small recursion or loop).

How Execution Grows With Input

As the tree grows taller, the number of steps to find and delete a node grows roughly with the tree height.

Input Size (n)	Approx. Operations
10	Up to 4-5 steps (tree height)
100	Up to 7-8 steps
1000	Up to 10-11 steps

Pattern observation: The steps grow slowly with input size if the tree is balanced, but can grow linearly if unbalanced.

Final Time Complexity

Time Complexity: O(h) where h is the tree height

This means the time depends on how tall the tree is, not just how many nodes it has.

Common Mistake

[X] Wrong: "Deleting a node always takes the same time regardless of tree shape."

[OK] Correct: If the tree is very unbalanced (like a linked list), deletion can take much longer because you must go through many nodes.

Interview Connect

Understanding how deletion time depends on tree height helps you explain trade-offs in tree design and shows you can analyze recursive code well.

Self-Check

"What if the BST is always perfectly balanced? How would the time complexity change then?"