BST Delete Operation in DSA Go - Time & Space Complexity

Time Complexity: BST Delete Operation

O(h)

Understanding Time Complexity

We want to understand how the time to delete a node in a Binary Search Tree (BST) changes as the tree grows.

Specifically, how does the number of steps needed to find and remove a node grow with the number of nodes?

Scenario Under Consideration

Analyze the time complexity of the following BST delete function.

func deleteNode(root *Node, key int) *Node {
    if root == nil {
        return nil
    }
    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 == nil {
            return root.right
        } else if root.right == nil {
            return root.left
        }
        minNode := findMin(root.right)
        root.val = minNode.val
        root.right = deleteNode(root.right, minNode.val)
    }
    return root
}

func findMin(node *Node) *Node {
    for node.left != nil {
        node = node.left
    }
    return node
}
    

This code deletes a node with a given key from a BST by searching for it, then handling three cases: no child, one child, or two children.

Identify Repeating Operations

Look for loops and recursion that repeat work.

• Primary operation: Recursive search down the tree to find the node to delete.
• How many times: At most once per level of the tree, moving down either left or right child.
• Additional operation: Finding the minimum node in the right subtree (findMin) which loops down left children.

How Execution Grows With Input

As the number of nodes (n) grows, the height of the tree affects how many steps we take.

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

Pattern observation: The steps grow roughly with the height of the tree, which depends on how balanced it is.

Final Time Complexity

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

This means the time to delete depends on how tall the tree is, not just the number of nodes.

Common Mistake

[X] Wrong: "Deleting a node always takes O(n) time because we might check every node."

[OK] Correct: We only follow one path down the tree, so we don't visit all nodes, just those along the height.

Interview Connect

Understanding how tree height affects delete operation time helps you explain efficiency clearly and shows you know how data structure shape impacts performance.

Self-Check

"What if the BST is always perfectly balanced? How does that change the time complexity of delete?"