BST Delete Operation in DSA Typescript - 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 grows as the tree gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following BST delete function.

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if (!root) return null;
  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;
    let minNode = findMin(root.right);
    root.val = minNode.val;
    root.right = deleteNode(root.right, minNode.val);
  }
  return root;
}

function findMin(node: TreeNode): TreeNode {
  while (node.left) node = node.left;
  return node;
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to traverse down the tree to find the node to delete.
• How many times: At most once per tree level, moving down one child each time.
• Additional operation: The findMin function loops down the left children of the right subtree.
• Dominant operation: The recursive traversal down the tree, which depends on tree height.

How Execution Grows With Input

As the tree grows, the number of steps depends on the height of the tree.

Input Size (n)	Approx. Operations (steps down tree)
10	About 3 to 4 steps
100	About 6 to 7 steps
1000	About 9 to 10 steps

Pattern observation: If the tree is balanced, steps grow slowly (logarithmically) as the tree size increases.

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 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 tree height affects delete operation 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 would that change the time complexity of delete?"