Binary Search Tree Operations

Name: Visualize DSA
Availability: OnlineOnly

Visualize Insert, Search, and Delete operations with step-by-step execution.

BST Selection

Tree Type

A basic binary search tree with a few nodes

Operation

Operation Type

Value

Value between 1 and 999

Playback Controls

Playback Speed: 1000ms

Step 1 of 1

Select a BST and operation to begin

Reference implementation of BST Operations. Select a language tab to view and copy the code.

Node* insert(Node* root, int val) {
    if (root == NULL)
        return newNode(val);            // create new node
    if (val < root->val)
        root->left  = insert(root->left,  val); // go left
    else if (val > root->val)
        root->right = insert(root->right, val); // go right
    return root;                        // return unchanged node
}
Node* search(Node* root, int val) {
    if (root == NULL)
        return NULL;                    // not found
    if (val == root->val)
        return root;                    // found
    if (val < root->val)
        return search(root->left,  val); // search left
    return search(root->right, val);     // search right
}
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)  return root->right;
        if (!root->right) return root->left;
        Node* succ  = findMin(root->right);
        root->val   = succ->val;
        root->right = delete(root->right, succ->val);
    }
    return root;
}

TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);  // create new node
    if (val < root->val)
        root->left  = insert(root->left,  val); // go left
    else if (val > root->val)
        root->right = insert(root->right, val); // go right
    return root;                           // return unchanged node
}
TreeNode* search(TreeNode* root, int val) {
    if (!root)            return nullptr; // not found
    if (val == root->val) return root;    // found
    if (val < root->val)
        return search(root->left,  val);  // search left
    return search(root->right, val);      // search right
}
TreeNode* remove(TreeNode* root, int val) {
    if (!root) return nullptr;
    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)  return root->right;
        if (!root->right) return root->left;
        TreeNode* succ = findMin(root->right);
        root->val      = succ->val;
        root->right    = remove(root->right, succ->val);
    }
    return root;
}

TreeNode insert(TreeNode root, int val) {
    if (root == null)
        return new TreeNode(val);       // create new node
    if (val < root.val)
        root.left  = insert(root.left,  val); // go left
    else if (val > root.val)
        root.right = insert(root.right, val); // go right
    return root;                        // return unchanged node
}
TreeNode search(TreeNode root, int val) {
    if (root == null)   return null;    // not found
    if (val == root.val) return root;   // found
    if (val < root.val)
        return search(root.left,  val); // search left
    return search(root.right, val);     // search right
}
TreeNode delete(TreeNode 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;
        TreeNode succ = findMin(root.right);
        root.val   = succ.val;
        root.right = delete(root.right, succ.val);
    }
    return root;
}

class BST:
    def insert(self, root, val):
        if root is None:
            return TreeNode(val)        # create new node
        if val < root.val:
            root.left  = self.insert(root.left,  val)  # go left
        elif val > root.val:
            root.right = self.insert(root.right, val)  # go right
        return root                     # return unchanged node

    def search(self, root, val):
        if root is None:
            return None                 # not found
        if val == root.val:
            return root                 # found
        if val < root.val:
            return self.search(root.left,  val)  # search left
        return self.search(root.right, val)      # search right

    def delete(self, root, val):
        if root is None: return None
        if val < root.val:
            root.left  = self.delete(root.left,  val)
        elif val > root.val:
            root.right = self.delete(root.right, val)
        else:                           # found node to delete
            if not root.left:  return root.right  # only right child
            if not root.right: return root.left   # only left child
            min_node = self._find_min(root.right) # in-order successor
            root.val   = min_node.val
            root.right = self.delete(root.right, min_node.val)
        return root

function insert(root, val) {
  if (!root) return new TreeNode(val);   // create new node
  if (val < root.val)
    root.left  = insert(root.left,  val); // go left
  else if (val > root.val)
    root.right = insert(root.right, val); // go right
  return root;                            // return unchanged node
}
function search(root, val) {
  if (!root)           return null;       // not found
  if (val === root.val) return root;       // found
  if (val < root.val)
    return search(root.left,  val);       // search left
  return search(root.right, val);         // search right
}
function remove(root, val) {
  if (!root) 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)  return root.right;   // only right child
    if (!root.right) return root.left;    // only left child
    const succ = findMin(root.right);     // in-order successor
    root.val   = succ.val;
    root.right = remove(root.right, succ.val);
  }
  return root;
}

Python — Code Walkthrough

Insert — recursive descent
if val < root.val: root.left = self.insert(root.left, val)
Compares val with the current node: go left if smaller, right if larger. When a None slot is reached, a new node is created there.
Search — O(log n) average
if val == root.val: return root
At each node, compare val with node.val. Equal → found; smaller → recurse left; larger → recurse right. Height of tree determines depth.
Delete — three cases
min_node = self._find_min(root.right)
No children → remove directly. One child → replace with that child. Two children → replace value with in-order successor (smallest in right subtree), then delete the successor.
In-order successor
root.val = min_node.val; root.right = self.delete(root.right, min_node.val)
Copy the in-order successor's value into the current node, then delete the successor from the right subtree (which has at most one child).