SimuVedaAlgorithms Lab Open in the lab

Trees / Intermediate

BST Delete Visualizer

Find the node. With zero or one child, its child takes its place. With two children, copy in the smallest value from the right subtree, then delete that one.

Start the BST Delete simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(log n)
Average timeO(log n)
Worst timeO(n)
Extra spaceO(h)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Delete 45.
  2. 45 < 50, so go left.
  3. 45 > 30, so go right.
  4. 45 > 40, so go right.
  5. Reached an empty spot. 45 is not in the tree.

Try it with your own input →

BST delete in Java, Python, C++, C and JavaScript

Node delete(Node root, int val) {
  if (root == null) return null;
  if (val < root.val) root.left = delete(root.left, val);
  else if (val > root.val) root.right = delete(root.right, val);
  else {
    if (root.left == null) return root.right;
    if (root.right == null) return root.left;
    Node s = minNode(root.right);
    root.val = s.val;
    root.right = delete(root.right, s.val);
  }
  return root;
}
def delete(root, val):
    if root is None:
        return None
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        s = min_node(root.right)
        root.val = s.val
        root.right = delete(root.right, s.val)
    return root
Node* del(Node* root, int val) {
  if (!root) return nullptr;
  if (val < root->val) root->left = del(root->left, val);
  else if (val > root->val) root->right = del(root->right, val);
  else {
    if (!root->left) { Node* r = root->right; delete root; return r; }
    if (!root->right) { Node* l = root->left; delete root; return l; }
    Node* s = minNode(root->right);
    root->val = s->val;
    root->right = del(root->right, s->val);
  }
  return root;
}
struct Node* del(struct Node* root, int val) {
  if (root == NULL) return NULL;
  if (val < root->val) root->left = del(root->left, val);
  else if (val > root->val) root->right = del(root->right, val);
  else {
    if (root->left == NULL) { struct Node* r = root->right; free(root); return r; }
    if (root->right == NULL) { struct Node* l = root->left; free(root); return l; }
    struct Node* s = minNode(root->right);
    root->val = s->val;
    root->right = del(root->right, s->val);
  }
  return root;
}
function remove(root, val) {
  if (root === null) return null;
  if (val < root.val) root.left = remove(root.left, val);
  else if (val > root.val) root.right = remove(root.right, val);
  else {
    if (root.left === null) return root.right;
    if (root.right === null) return root.left;
    const s = minNode(root.right);
    root.val = s.val;
    root.right = remove(root.right, s.val);
  }
  return root;
}

In an interview

The two-children case is the one interviewers ask about. Delete the root here to see it.

More trees