BST Delete Operation in DSA Javascript

Mental Model

Deleting a node from a BST means removing it while keeping the tree sorted. We find the node, then rearrange its children carefully.

Analogy: Imagine removing a book from a sorted shelf. If the book has no neighbors, just take it out. If it has one neighbor, slide that neighbor in. If it has two neighbors, replace it with the closest bigger book and remove that one instead.

      5
     / \
    3   7
   / \   \
  2   4   8

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, delete node with value 3

Goal: Remove node 3 and keep BST properties intact

Step 1: Find node 3 starting from root 5

      5 ↑
     / \
    3   7
   / \   \
  2   4   8

Why: We need to locate the node to delete

Step 2: Node 3 has two children (2 and 4), find its inorder successor (smallest in right subtree)

      5
     / \
    3 ↑ 7
   / \   \
  2   4   8

Why: To keep BST order, replace node 3 with its inorder successor

Step 3: Inorder successor is node 4 (right child of 3)

      5
     / \
    3   7
   / \   \
  2  ↑4   8

Why: We pick the smallest node in right subtree to replace node 3

Step 4: Replace node 3's value with 4, then delete node 4 which has no children

      5
     / \
    4   7
   /     \
  2       8

Why: Replacing value keeps BST order; deleting leaf node 4 is simple

Result:

      5
     / \
    4   7
   /     \
  2       8

Annotated Code

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(val) {
    const newNode = new Node(val);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let curr = this.root;
    while (true) {
      if (val < curr.val) {
        if (!curr.left) {
          curr.left = newNode;
          return;
        }
        curr = curr.left;
      } else {
        if (!curr.right) {
          curr.right = newNode;
          return;
        }
        curr = curr.right;
      }
    }
  }

  delete(val) {
    this.root = this._deleteRec(this.root, val);
  }

  _deleteRec(node, val) {
    if (!node) return null; // base case: node not found

    if (val < node.val) {
      node.left = this._deleteRec(node.left, val); // go left
    } else if (val > node.val) {
      node.right = this._deleteRec(node.right, val); // go right
    } else {
      // node found
      if (!node.left && !node.right) {
        return null; // no children, remove node
      } else if (!node.left) {
        return node.right; // only right child, replace node
      } else if (!node.right) {
        return node.left; // only left child, replace node
      } else {
        // two children: find inorder successor
        let succ = this._minValueNode(node.right);
        node.val = succ.val; // replace value
        node.right = this._deleteRec(node.right, succ.val); // delete successor
      }
    }
    return node;
  }

  _minValueNode(node) {
    let current = node;
    while (current.left) {
      current = current.left; // go left to find min
    }
    return current;
  }

  inorder() {
    const res = [];
    function traverse(node) {
      if (!node) return;
      traverse(node.left);
      res.push(node.val);
      traverse(node.right);
    }
    traverse(this.root);
    return res.join(' -> ') + ' -> null';
  }
}

// Driver code
const bst = new BST();
[5,3,7,2,4,8].forEach(v => bst.insert(v));
bst.delete(3);
console.log(bst.inorder());

if (!node) return null; // base case: node not found

stop recursion when node is null

if (val < node.val) { node.left = this._deleteRec(node.left, val); // go left }

search left subtree for node to delete

else if (val > node.val) { node.right = this._deleteRec(node.right, val); // go right }

search right subtree for node to delete

if (!node.left && !node.right) { return null; // no children, remove node }

delete leaf node by returning null

else if (!node.left) { return node.right; // only right child, replace node }

replace node with right child if no left child

else if (!node.right) { return node.left; // only left child, replace node }

replace node with left child if no right child

let succ = this._minValueNode(node.right); node.val = succ.val; node.right = this._deleteRec(node.right, succ.val);

replace node value with inorder successor and delete successor

while (current.left) { current = current.left; // go left to find min }

find minimum value node in right subtree

Output

2 -> 4 -> 5 -> 7 -> 8 -> null

Complexity Analysis

Time: O(h) where h is tree height because we traverse from root to node and possibly to successor

Space: O(h) due to recursion stack in worst case of skewed tree

vs Alternative: Compared to naive approach of rebuilding tree after deletion, this is efficient as it only adjusts necessary nodes

Edge Cases

Deleting a node not present in the tree

Function returns without changes, no error

DSA Javascript

if (!node) return null; // base case: node not found

Deleting a leaf node (no children)

Node is simply removed by returning null

DSA Javascript

if (!node.left && !node.right) {
  return null; // no children, remove node
}

Deleting node with only one child

Node is replaced by its single child

DSA Javascript

else if (!node.left) {
  return node.right; // only right child, replace node
}

When to Use This Pattern

When you need to remove a node from a BST and keep it sorted, use the BST delete pattern that handles 0, 1, or 2 children cases carefully.

Common Mistakes

Mistake: Not handling the two children case by replacing with inorder successor
Fix: Always find the inorder successor (smallest in right subtree) and replace node's value before deleting successor

Mistake: Not updating parent's child pointer after deletion
Fix: Return the updated subtree root from recursive calls and assign it back to parent's left or right pointer

Summary

Deletes a node from a BST while maintaining the BST property.

Use when you need to remove a value from a BST without breaking its order.

The key is to replace a node with two children by its inorder successor and then delete that successor.

Practice

1. What happens when you delete a leaf node (a node with no children) from a Binary Search Tree (BST)?

easy

A. The node is simply removed without affecting other nodes.

B. The entire tree is rebuilt from scratch.

C. The node's children replace it in the tree.

D. The root node is always changed.

Solution

1. Step 1: Understand leaf node deletion

   A leaf node has no children, so removing it does not affect other nodes.

2. Step 2: Effect on BST structure

   Since no children exist, simply remove the node and update its parent's pointer to null.

3. Final Answer:

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

4. Quick Check:

   Leaf node deletion = simple removal [OK]

Hint: Leaf nodes delete by direct removal only [OK]

Common Mistakes:

• Thinking children replace the node when none exist
• Assuming root always changes
• Believing tree rebuild is needed

2. Which of the following is the correct syntax to delete a node with value key from a BST in JavaScript?

easy

A. bst.deleteNode(key);

B. bst.delete(key);

C. bst.remove(key);

D. bst.erase(key);

Solution

1. Step 1: Identify common BST delete method

   In many JavaScript BST implementations, the method to delete a node is named delete.

2. Step 2: Check method naming conventions

   Methods like remove, erase, or deleteNode are not standard or common in JavaScript BST examples.

3. Final Answer:

   bst.delete(key); -> Option B

4. Quick Check:

   Standard BST delete method = delete() [OK]

Hint: Use bst.delete(key) to remove nodes [OK]

Common Mistakes:

• Using remove() or erase() which are not standard
• Confusing delete keyword with method name
• Using deleteNode() which is uncommon

3. Consider this BST and the delete operation:

    10
   /  \
  5    15
       / \
      12  20

What will be the in-order traversal output after deleting node with value 15?

medium

A. [5, 10, 12, 15, 20]

B. [5, 10, 20]

C. [5, 10, 12, 20]

D. [5, 10, 15, 20]

Solution

1. Step 1: Identify node to delete and its children

   Node 15 has two children: 12 (left) and 20 (right).

2. Step 2: Replace node 15 with its in-order successor

   The in-order successor is the smallest node in right subtree, which is 20. Replace 15 with 20 and delete original 20 node.

3. Step 3: Perform in-order traversal

   In-order traversal visits nodes in ascending order: 5, 10, 12, 20.

4. Final Answer:

   [5, 10, 12, 20] -> Option C

5. Quick Check:

   In-order after deleting 15 = [5, 10, 12, 20] [OK]

Hint: Replace deleted node with in-order successor [OK]

Common Mistakes:

• Removing 15 without replacement
• Using in-order predecessor instead of successor
• Forgetting to delete the successor node

4. The following code attempts to delete a node from a BST but causes an error. What is the main issue?

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;
    else if (!root.right) return root.left;
    let minNode = findMin(root.right);
    root.val = minNode.val;
    // Missing deletion of minNode here
  }
  return root;
}

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

medium

A. The function does not handle leaf nodes correctly.

B. The base case for recursion is missing.

C. The function uses incorrect comparison operators.

D. The code does not delete the in-order successor node after copying its value.

Solution

1. Step 1: Analyze deletion of node with two children

   When deleting a node with two children, we replace its value with the in-order successor's value.

2. Step 2: Check if in-order successor node is deleted

   The code copies the successor's value but does not delete the successor node itself, causing duplicate values and incorrect tree.

3. Final Answer:

   The code does not delete the in-order successor node after copying its value. -> Option D

4. Quick Check:

   Must delete successor node after value copy [OK]

Hint: Always delete successor node after copying value [OK]

Common Mistakes:

• Forgetting to delete the in-order successor node
• Missing base case (though present here)
• Incorrectly handling leaf nodes
• Using wrong comparison operators

5. You have a BST with nodes: 8, 3, 10, 1, 6, 14, 4, 7, 13.
After deleting node 3, what is the correct in-order traversal of the BST?

hard

A. [1, 4, 6, 7, 8, 10, 13, 14]

B. [1, 3, 4, 6, 7, 8, 10, 13, 14]

C. [1, 6, 7, 8, 10, 13, 14]

D. [1, 4, 7, 8, 10, 13, 14]

Solution

1. Step 1: Identify node 3 and its children

   Node 3 has two children: 1 (left) and 6 (right). 6 has children 4 and 7.

2. Step 2: Delete node 3 by replacing with in-order successor

   The in-order successor of 3 is 4 (smallest in right subtree). Replace 3 with 4, then delete original 4 node.

3. Step 3: Perform in-order traversal after deletion

   In-order traversal visits nodes in ascending order: 1, 4, 6, 7, 8, 10, 13, 14.

4. Final Answer:

   [1, 4, 6, 7, 8, 10, 13, 14] -> Option A

5. Quick Check:

   In-order after deleting 3 = [1, 4, 6, 7, 8, 10, 13, 14] [OK]

Hint: Replace deleted node with in-order successor, then traverse [OK]

Common Mistakes:

• Forgetting to delete the in-order successor node
• Using in-order predecessor instead
• Skipping nodes in traversal