BST Delete Operation in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after deleting a leaf node in BST

What is the printed state of the BST after deleting the leaf node with value 20?

DSA Javascript

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

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

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

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

  _deleteRec(root, data) {
    if (!root) return root;
    if (data < root.data) {
      root.left = this._deleteRec(root.left, data);
    } else if (data > root.data) {
      root.right = this._deleteRec(root.right, data);
    } else {
      if (!root.left && !root.right) {
        return null;
      } else if (!root.left) {
        return root.right;
      } else if (!root.right) {
        return root.left;
      } else {
        let minLargerNode = this._minValueNode(root.right);
        root.data = minLargerNode.data;
        root.right = this._deleteRec(root.right, minLargerNode.data);
      }
    }
    return root;
  }

  _minValueNode(node) {
    let current = node;
    while (current.left) {
      current = current.left;
    }
    return current;
  }

  inorder(root = this.root, result = []) {
    if (root) {
      this.inorder(root.left, result);
      result.push(root.data);
      this.inorder(root.right, result);
    }
    return result;
  }

  print() {
    const values = this.inorder();
    console.log(values.join(' -> ') + ' -> null');
  }
}

const bst = new BST();
[50, 30, 70, 20, 40, 60, 80].forEach(n => bst.insert(n));
bst.delete(20);
bst.print();

A 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

B 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

C 50 -> 30 -> 40 -> 60 -> 70 -> 80 -> null

D 30 -> 40 -> 50 -> 60 -> 70 -> null

💡 Hint

Deleting a leaf node removes it without affecting other nodes.

Deleting 20 removes the leaf node 20. The inorder traversal then lists nodes in ascending order without 20.

❓ Predict Output

intermediate

Output after deleting a node with one child in BST

What is the printed state of the BST after deleting the node with value 30, which has one child?

DSA Javascript

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

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

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

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

  _deleteRec(root, data) {
    if (!root) return root;
    if (data < root.data) {
      root.left = this._deleteRec(root.left, data);
    } else if (data > root.data) {
      root.right = this._deleteRec(root.right, data);
    } else {
      if (!root.left && !root.right) {
        return null;
      } else if (!root.left) {
        return root.right;
      } else if (!root.right) {
        return root.left;
      } else {
        let minLargerNode = this._minValueNode(root.right);
        root.data = minLargerNode.data;
        root.right = this._deleteRec(root.right, minLargerNode.data);
      }
    }
    return root;
  }

  _minValueNode(node) {
    let current = node;
    while (current.left) {
      current = current.left;
    }
    return current;
  }

  inorder(root = this.root, result = []) {
    if (root) {
      this.inorder(root.left, result);
      result.push(root.data);
      this.inorder(root.right, result);
    }
    return result;
  }

  print() {
    const values = this.inorder();
    console.log(values.join(' -> ') + ' -> null');
  }
}

const bst = new BST();
[50, 30, 70, 40, 60, 80].forEach(n => bst.insert(n));
bst.delete(30);
bst.print();

A 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

B 40 -> 50 -> 60 -> 70 -> 80 -> null

C 50 -> 40 -> 60 -> 70 -> 80 -> null

D 40 -> 30 -> 50 -> 60 -> 70 -> 80 -> null

💡 Hint

When deleting a node with one child, the child replaces the node.

Node 30 has one child 40. After deletion, 40 replaces 30. The inorder traversal is [40, 50, 60, 70, 80].

❓ Predict Output

advanced

Output after deleting a node with two children in BST

What is the printed state of the BST after deleting the node with value 50, which has two children?

DSA Javascript

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

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

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

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

  _deleteRec(root, data) {
    if (!root) return root;
    if (data < root.data) {
      root.left = this._deleteRec(root.left, data);
    } else if (data > root.data) {
      root.right = this._deleteRec(root.right, data);
    } else {
      if (!root.left && !root.right) {
        return null;
      } else if (!root.left) {
        return root.right;
      } else if (!root.right) {
        return root.left;
      } else {
        let minLargerNode = this._minValueNode(root.right);
        root.data = minLargerNode.data;
        root.right = this._deleteRec(root.right, minLargerNode.data);
      }
    }
    return root;
  }

  _minValueNode(node) {
    let current = node;
    while (current.left) {
      current = current.left;
    }
    return current;
  }

  inorder(root = this.root, result = []) {
    if (root) {
      this.inorder(root.left, result);
      result.push(root.data);
      this.inorder(root.right, result);
    }
    return result;
  }

  print() {
    const values = this.inorder();
    console.log(values.join(' -> ') + ' -> null');
  }
}

const bst = new BST();
[50, 30, 70, 20, 40, 60, 80].forEach(n => bst.insert(n));
bst.delete(50);
bst.print();

A 20 -> 30 -> 40 -> 60 -> 70 -> 80 -> null

B 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

C 20 -> 30 -> 40 -> 60 -> 70 -> 80 -> 50 -> null

D 30 -> 40 -> 60 -> 70 -> 80 -> null

💡 Hint

When deleting a node with two children, replace it with the smallest node in the right subtree.

Node 50 is replaced by 60 (smallest in right subtree). Then 60 is deleted from its original position. The inorder traversal is [20, 30, 40, 60, 70, 80].

🧠 Conceptual

advanced

Understanding BST delete operation cases

Which of the following correctly describes the three main cases when deleting a node from a BST?

A Node is left child; node is right child; node is root

B Node is root; node is leaf; node is internal

C Node has no children; node has left child only; node has right child only

D Node is a leaf; node has one child; node has two children

💡 Hint

Think about how many children the node to delete can have.

The three main cases are deleting a leaf node (no children), a node with one child, and a node with two children.

🔧 Debug

expert

Identify the bug in BST delete operation code

Given the following snippet from a BST delete function, what is the bug causing incorrect deletion when the node has two children? ```js _deleteRec(root, data) { if (!root) return root; if (data < root.data) { root.left = this._deleteRec(root.left, data); } else if (data > root.data) { root.right = this._deleteRec(root.right, data); } else { if (!root.left && !root.right) { return null; } else if (!root.left) { return root.right; } else if (!root.right) { return root.left; } else { let minLargerNode = this._minValueNode(root.right); root.data = minLargerNode.data; root.left = this._deleteRec(root.right, minLargerNode.data); } } return root; } ``` What is the bug?

A The base case should return null instead of root

B The function does not handle leaf nodes correctly

C The recursive call after replacing data should update root.right, not root.left

D The minimum value node is found incorrectly from the left subtree

💡 Hint

Check which subtree is updated after replacing the node's data.

After replacing the node's data with the minimum from the right subtree, the deletion must continue in the right subtree. The code incorrectly updates root.left instead of root.right.