Bird
Raised Fist0
DSA Typescriptprogramming~5 mins

BST Delete Operation in DSA Typescript - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
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)
10About 3 to 4 steps
100About 6 to 7 steps
1000About 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?"

Practice

(1/5)
1. What happens when you delete a leaf node (a node with no children) in a Binary Search Tree (BST)?
easy
A. The entire tree is rebuilt
B. The node is replaced by its right child
C. The node is replaced by its left child
D. The node is simply removed without affecting other nodes

Solution

  1. Step 1: Understand leaf node deletion

    A leaf node has no children, so deleting it means just removing it from the tree.

  2. Step 2: Effect on the BST

    Since it has no children, no other nodes need to be moved or replaced.

  3. Final Answer:

    The node is simply removed without affecting other nodes -> Option D

  4. Quick Check:

    Leaf node deletion = simple removal [OK]
Hint: Leaf nodes delete by direct removal only [OK]
Common Mistakes:
  • Thinking children need rearrangement
  • Replacing leaf with child nodes
  • Rebuilding the whole tree
2. Which of the following is the correct TypeScript function signature for deleting a node from a BST?
easy
A. function deleteNode(key: number): TreeNode
B. function deleteNode(root: number, key: TreeNode): void
C. function deleteNode(root: TreeNode | null, key: number): TreeNode | null
D. function deleteNode(root: TreeNode, key: string): TreeNode

Solution

  1. Step 1: Analyze parameter types

    The root should be a TreeNode or null, and key should be a number to identify the node.

  2. Step 2: Analyze return type

    The function returns the updated root node or null if tree becomes empty.

  3. Final Answer:

    function deleteNode(root: TreeNode | null, key: number): TreeNode | null -> Option C

  4. Quick Check:

    Correct parameter and return types = function deleteNode(root: TreeNode | null, key: number): TreeNode | null [OK]
Hint: Root can be null; key is number; returns updated root [OK]
Common Mistakes:
  • Swapping parameter types
  • Using wrong return type
  • Using string instead of number for key
3. Given the BST below and the delete operation deleteNode(root, 10), what is the in-order traversal of the BST after deletion?

BST structure:
15
/ \
10 20
/ \ \
8 12 25
medium
A. [8, 12, 15, 20, 25]
B. [8, 10, 12, 15, 20, 25]
C. [8, 15, 20, 25]
D. [12, 15, 20, 25]

Solution

  1. Step 1: Delete node 10 with two children

    Node 10 has two children (8 and 12). Replace it with its inorder successor, which is 12.

  2. Step 2: Remove node 12 from its original position

    After replacement, remove node 12 from right subtree of 10.

  3. Step 3: In-order traversal after deletion

    Traversal is [8, 12, 15, 20, 25].

  4. Final Answer:

    [8, 12, 15, 20, 25] -> Option A

  5. Quick Check:

    Inorder after deleting 10 = [8, 12, 15, 20, 25] [OK]
Hint: Replace node with inorder successor for two children [OK]
Common Mistakes:
  • Not replacing node 10 correctly
  • Leaving node 10 in tree
  • Incorrect traversal order
4. Consider this TypeScript code snippet for deleting a node from a BST. What is the bug?
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;
    deleteNode(root.right, minNode.val);
  }
  return root;
}
medium
A. No return statement after deletion
B. Missing assignment of root.right after deleting minNode
C. Wrong comparison operators for key
D. Incorrect base case for empty root

Solution

  1. Step 1: Analyze deletion of minNode

    After copying minNode's value, the code calls deleteNode on root.right but does not assign the result back to root.right.

  2. Step 2: Effect of missing assignment

    Without assignment, the minNode is not removed from the right subtree, causing duplicate values.

  3. Final Answer:

    Missing assignment of root.right after deleting minNode -> Option B

  4. Quick Check:

    Assign updated subtree after deletion [OK]
Hint: Always assign recursive delete result back to subtree [OK]
Common Mistakes:
  • Forgetting to assign after recursive delete
  • Misplacing base case
  • Using wrong comparison signs
5. You have a BST with nodes: 30, 20, 40, 10, 25, 35, 50. You delete node 30 (root). Which node becomes the new root after deletion using the standard BST delete operation?
hard
A. 35
B. 25
C. 40
D. 20

Solution

  1. Step 1: Identify node 30's children

    Node 30 has two children: left subtree with 20 and right subtree with 40.

  2. Step 2: Find inorder successor of 30

    Inorder successor is the smallest node in right subtree, which is 35.

  3. Step 3: Replace 30 with 35 and delete 35 from right subtree

    35 replaces 30 as root, and 35 is removed from its original position.

  4. Final Answer:

    35 -> Option A

  5. Quick Check:

    Inorder successor replaces deleted node [OK]
Hint: Use inorder successor (smallest right subtree) for two-child node deletion [OK]
Common Mistakes:
  • Using inorder predecessor instead
  • Choosing wrong replacement node
  • Not updating root after deletion
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard