← Back to DSA Course | Chapter 11: Trees | Lesson 5 of 10

BST Insert Delete Search

In this page:

  1. Insertion
  2. Search
  3. Deletion
  4. Replacement in Deletion
  5. BST Operations Practice

Insertion

Inserting a value into a BST follows the same left/right comparison logic as searching, walking down the tree until an empty spot consistent with the ordering rule is found, and placing the new node there.

Example: Insertion

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* insert(Node* n, int v) {
    if (!n) return new Node{v, nullptr, nullptr};
    if (v < n->val) n->left = insert(n->left, v);
    else n->right = insert(n->right, v);
    return n;
}
int main() {
    Node* root = new Node{5, nullptr, nullptr};
    root = insert(root, 3);
    root = insert(root, 8);
    cout << "Inserted 3 and 8: left=" << root->left->val << " right=" << root->right->val << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node insert(Node n, int v) {
        if (n == null) return new Node(v);
        if (v < n.val) n.left = insert(n.left, v);
        else n.right = insert(n.right, v);
        return n;
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root = insert(root, 3);
        root = insert(root, 8);
        System.out.println("Inserted 3 and 8: left=" + root.left.val + " right=" + root.right.val);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def insert(n, v):
    if n is None:
        return Node(v)
    if v < n.val:
        n.left = insert(n.left, v)
    else:
        n.right = insert(n.right, v)
    return n

root = Node(5)
root = insert(root, 3)
root = insert(root, 8)
print("Inserted 3 and 8: left=", root.left.val, "right=", root.right.val)
#include <stdio.h>
#include <stdlib.h>
struct Node { int val; struct Node *left, *right; };
struct Node* insert(struct Node* n, int v) {
    if (!n) {
        struct Node* nn = malloc(sizeof(struct Node));
        nn->val = v; nn->left = nn->right = NULL;
        return nn;
    }
    if (v < n->val) n->left = insert(n->left, v);
    else n->right = insert(n->right, v);
    return n;
}
int main() {
    struct Node* root = malloc(sizeof(struct Node));
    root->val = 5; root->left = root->right = NULL;
    root = insert(root, 3);
    root = insert(root, 8);
    printf("Inserted 3 and 8: left=%d right=%d\n", root->left->val, root->right->val);
    return 0;
}

Search

Searching a BST moves left or right at each node based on comparing the target key against the current node's value, stopping either when a match is found or when it reaches a missing child, meaning the value isn't present.

Example: Search

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
bool search(Node* n, int target) {
    if (!n) return false;
    if (n->val == target) return true;
    return target < n->val ? search(n->left, target) : search(n->right, target);
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << (search(&root, 8) ? "Found" : "Not found") << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static boolean search(Node n, int target) {
        if (n == null) return false;
        if (n.val == target) return true;
        return target < n.val ? search(n.left, target) : search(n.right, target);
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println(search(root, 8) ? "Found" : "Not found");
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def search(n, target):
    if n is None:
        return False
    if n.val == target:
        return True
    return search(n.left, target) if target < n.val else search(n.right, target)

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("Found" if search(root, 8) else "Not found")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int search(struct Node* n, int target) {
    if (!n) return 0;
    if (n->val == target) return 1;
    return target < n->val ? search(n->left, target) : search(n->right, target);
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("%s\n", search(&root, 8) ? "Found" : "Not found");
    return 0;
}

Deletion

Deleting a node has three distinct cases: a leaf node can simply be removed, a node with one child can be replaced directly by that child, but a node with two children needs special handling since removing it would break the tree's structure.

Example: Deletion

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
    cout << "Leaf: remove directly. One child: replace with that child. Two children: replace with inorder successor." << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Leaf: remove directly. One child: replace with that child. Two children: replace with inorder successor.");
    }
}
print("Leaf: remove directly. One child: replace with that child. Two children: replace with inorder successor.")
#include <stdio.h>
int main() {
    printf("Leaf: remove directly. One child: replace with that child. Two children: replace with inorder successor.\n");
    return 0;
}

Replacement in Deletion

For a node with two children, the standard fix is to replace its value with its inorder successor (the smallest value in its right subtree, found by following left children from there) and then delete that successor node instead, which is guaranteed to have at most one child.

Example: Replacement in Deletion

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* findMin(Node* n) { while (n->left) n = n->left; return n; }
int main() {
    Node a={9,nullptr,nullptr}, b={7,&a,nullptr};
    Node root={5,nullptr,&b};
    cout << "Inorder successor of root (smallest in right subtree): " << findMin(root.right)->val << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node findMin(Node n) { while (n.left != null) n = n.left; return n; }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.right = new Node(7);
        root.right.left = new Node(9);
        System.out.println("Inorder successor of root (smallest in right subtree): " + findMin(root.right).val);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def find_min(n):
    while n.left: n = n.left
    return n

root = Node(5)
root.right = Node(7)
root.right.left = Node(9)
print("Inorder successor of root (smallest in right subtree):", find_min(root.right).val)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* findMin(struct Node* n) { while (n->left) n = n->left; return n; }
int main() {
    struct Node a={9,NULL,NULL}, b={7,&a,NULL};
    struct Node root={5,NULL,&b};
    printf("Inorder successor of root (smallest in right subtree): %d\n", findMin(root.right)->val);
    return 0;
}

BST Operations Practice

Insertion, search, and deletion together form the complete operational toolkit of a BST — all three run in time proportional to the tree's height, which is why keeping that height small (via a balanced tree) matters so much in practice.

Example: BST Operations Practice

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int height(Node* n) { if(!n) return 0; int l=height(n->left), r=height(n->right); return 1+(l>r?l:r); }
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "Insert/search/delete all run in O(height) = O(" << height(&root) << ") here" << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static int height(Node n) { if(n==null) return 0; return 1+Math.max(height(n.left),height(n.right)); }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("Insert/search/delete all run in O(height) = O(" + height(root) + ") here");
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def height(n):
    if n is None: return 0
    return 1 + max(height(n.left), height(n.right))

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("Insert/search/delete all run in O(height) = O(", height(root), ") here")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int height(struct Node* n) { if(!n) return 0; int l=height(n->left), r=height(n->right); return 1+(l>r?l:r); }
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("Insert/search/delete all run in O(height) = O(%d) here\n", height(&root));
    return 0;
}
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Binary Search Tree Next Lesson → AVL Tree

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.