BST Delete Operation in DSA Javascript - 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.

function deleteNode(root, key) {
  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 minLargerNode = root.right;
    while (minLargerNode.left) minLargerNode = minLargerNode.left;
    root.val = minLargerNode.val;
    root.right = deleteNode(root.right, minLargerNode.val);
  }
  return root;
}
    

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

Identify Repeating Operations

• Primary operation: Recursive search 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 smallest node in the right subtree (while loop) when deleting a node with two children.

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's height.

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

Pattern observation: The steps grow slowly as the tree grows, depending on how balanced it is.

Final Time Complexity

Time Complexity: O(h)

This means the time to delete depends on the tree height, which is the number of levels from root to leaf.

Common Mistake

[X] Wrong: "Deleting a node always takes the same time no matter the tree size."

[OK] Correct: The time depends on how tall the tree is. A taller tree means more steps to find and fix nodes.

Interview Connect

Understanding how delete works in BSTs helps you show you know tree operations well, a common topic in interviews.

Self-Check

"What if the BST is always perfectly balanced? How would that affect the delete operation's time complexity?"