DSA Javascriptprogramming

BST Delete Operation in DSA Javascript

Choose your learning style9 modes available

Learn Why Deep Visual Try Challenge Project Recall Time

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.

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

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)

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

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

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

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

Result:

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

OutputSuccess

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.