BST Delete Operation in DSA Typescript - 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 2?

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(val: number) {
    this.root = this._insert(this.root, val);
  }

  private _insert(root: Node | null, val: number): Node {
    if (!root) return new Node(val);
    if (val < root.val) root.left = this._insert(root.left, val);
    else root.right = this._insert(root.right, val);
    return root;
  }

  delete(val: number) {
    this.root = this._delete(this.root, val);
  }

  private _delete(root: Node | null, val: number): Node | null {
    if (!root) return null;
    if (val < root.val) root.left = this._delete(root.left, val);
    else if (val > root.val) root.right = this._delete(root.right, val);
    else {
      if (!root.left && !root.right) return null;
      if (!root.left) return root.right;
      if (!root.right) return root.left;
      let minLargerNode = this._minValueNode(root.right);
      root.val = minLargerNode.val;
      root.right = this._delete(root.right, minLargerNode.val);
    }
    return root;
  }

  private _minValueNode(root: Node): Node {
    while (root.left) root = root.left;
    return root;
  }

  printInOrder() {
    const result: number[] = [];
    function inorder(node: Node | null) {
      if (!node) return;
      inorder(node.left);
      result.push(node.val);
      inorder(node.right);
    }
    inorder(this.root);
    console.log(result.join(' -> ') + ' -> null');
  }
}

const bst = new BST();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
bst.insert(4);
bst.delete(2);
bst.printInOrder();

A 3 -> 4 -> 5 -> 7 -> null

B 2 -> 3 -> 4 -> 5 -> 7 -> null

C 3 -> 5 -> 7 -> null

D 4 -> 5 -> 7 -> null

💡 Hint

Deleting a leaf node removes it without affecting other nodes.

Node 2 is a leaf and gets removed. The in-order traversal then prints nodes in ascending order without 2.

❓ 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 3 which has one child?

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(val: number) {
    this.root = this._insert(this.root, val);
  }

  private _insert(root: Node | null, val: number): Node {
    if (!root) return new Node(val);
    if (val < root.val) root.left = this._insert(root.left, val);
    else root.right = this._insert(root.right, val);
    return root;
  }

  delete(val: number) {
    this.root = this._delete(this.root, val);
  }

  private _delete(root: Node | null, val: number): Node | null {
    if (!root) return null;
    if (val < root.val) root.left = this._delete(root.left, val);
    else if (val > root.val) root.right = this._delete(root.right, val);
    else {
      if (!root.left && !root.right) return null;
      if (!root.left) return root.right;
      if (!root.right) return root.left;
      let minLargerNode = this._minValueNode(root.right);
      root.val = minLargerNode.val;
      root.right = this._delete(root.right, minLargerNode.val);
    }
    return root;
  }

  private _minValueNode(root: Node): Node {
    while (root.left) root = root.left;
    return root;
  }

  printInOrder() {
    const result: number[] = [];
    function inorder(node: Node | null) {
      if (!node) return;
      inorder(node.left);
      result.push(node.val);
      inorder(node.right);
    }
    inorder(this.root);
    console.log(result.join(' -> ') + ' -> null');
  }
}

const bst = new BST();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(4);
bst.delete(3);
bst.printInOrder();

A 3 -> 4 -> 5 -> 7 -> null

B 4 -> 5 -> 7 -> null

C 5 -> 7 -> null

D 4 -> 7 -> null

💡 Hint

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

Node 3 has one child (4). After deletion, 4 takes 3's place. The in-order traversal reflects this.

❓ 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 5 which has two children?

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(val: number) {
    this.root = this._insert(this.root, val);
  }

  private _insert(root: Node | null, val: number): Node {
    if (!root) return new Node(val);
    if (val < root.val) root.left = this._insert(root.left, val);
    else root.right = this._insert(root.right, val);
    return root;
  }

  delete(val: number) {
    this.root = this._delete(this.root, val);
  }

  private _delete(root: Node | null, val: number): Node | null {
    if (!root) return null;
    if (val < root.val) root.left = this._delete(root.left, val);
    else if (val > root.val) root.right = this._delete(root.right, val);
    else {
      if (!root.left && !root.right) return null;
      if (!root.left) return root.right;
      if (!root.right) return root.left;
      let minLargerNode = this._minValueNode(root.right);
      root.val = minLargerNode.val;
      root.right = this._delete(root.right, minLargerNode.val);
    }
    return root;
  }

  private _minValueNode(root: Node): Node {
    while (root.left) root = root.left;
    return root;
  }

  printInOrder() {
    const result: number[] = [];
    function inorder(node: Node | null) {
      if (!node) return;
      inorder(node.left);
      result.push(node.val);
      inorder(node.right);
    }
    inorder(this.root);
    console.log(result.join(' -> ') + ' -> null');
  }
}

const bst = new BST();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
bst.insert(4);
bst.insert(6);
bst.insert(8);
bst.delete(5);
bst.printInOrder();

A 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> null

B 2 -> 3 -> 4 -> 7 -> 8 -> null

C 3 -> 4 -> 6 -> 7 -> 8 -> null

D 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null

💡 Hint

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

Node 5 is replaced by 6 (smallest in right subtree). Then 6 is deleted from its original position. The in-order traversal shows the updated tree.

🔧 Debug

advanced

Identify the error in BST delete method

What error will this code raise when trying to delete a node in the BST?

DSA Typescript

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

class BST {
  root: Node | null = null;

  delete(val: number) {
    this.root = this._delete(this.root, val);
  }

  private _delete(root: Node | null, val: number): Node | null {
    if (!root) return null;
    if (val < root.val) root.left = this._delete(root.left, val);
    else if (val > root.val) root.right = this._delete(root.right, val);
    else {
      if (!root.left && !root.right) return null;
      if (!root.left) return root.right;
      if (!root.right) return root.left;
      let minLargerNode = this._minValueNode(root.right);
      root.val = minLargerNode.val;
      root.right = this._delete(root.right, minLargerNode.val);
    }
    return root;
  }

  private _minValueNode(root: Node): Node {
    while (root.left) root = root.left;
    return root;
  }
}

const bst = new BST();
bst.delete(10);

A SyntaxError: Unexpected token

B No error, deletion works fine

C ReferenceError: _delete is not defined

D TypeError: Cannot read property 'val' of null

💡 Hint

Deleting from an empty tree tries to access properties of null.

Calling delete on an empty BST leads to _delete called with null root. The code tries to access root.val which causes a TypeError.

🧠 Conceptual

expert

Number of nodes after multiple deletions in BST

Given a BST with nodes inserted in this order: 10, 5, 15, 3, 7, 12, 18. After deleting nodes 5 and 15, how many nodes remain in the BST?

A 6

B 7

C 5

D 4

💡 Hint

Each deletion removes exactly one node from the tree.

Initially 7 nodes. Deleting 5 and 15 removes 2 nodes. Remaining nodes = 7 - 2 = 5.