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

BST में Insert, Delete और Search

एक BST में insert, delete और search करना tree में चलने जैसा है, compare करके left या right turn करते हुए, जब तक आप सही spot न ढूंढें।

In this page:

  1. Insertion
  2. Search
  3. Deletion
  4. Replacement in Deletion
  5. BST Operations Practice
Syntax
markup 
def insert(node, key):
    if node is None:
        return TreeNode(key)
    if key < node.value:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    return node

Insertion

किसी BST में एक value insert करना searching जैसा ही left/right comparison logic follow करता है, tree में तब तक चलते हुए जब तक ordering rule से consistent एक खाली spot न मिले, और नया node वहां रखते हुए।

उदाहरण: 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

किसी BST को search करना target key की current node की value से comparison के आधार पर हर node पर left या right move करता है, या तो एक match मिलने पर या एक missing child तक पहुंचने पर रुकते हुए, मतलब value मौजूद नहीं है।

उदाहरण: 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

किसी node को delete करने के तीन distinct cases हैं: एक leaf node को बस हटाया जा सकता है, एक child वाले node को सीधे उस child से replace किया जा सकता है, लेकिन दो children वाले node को special handling चाहिए क्योंकि इसे हटाना tree की structure तोड़ देगा।

उदाहरण: 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

दो children वाले node के लिए, standard fix इसकी value को इसके inorder successor (इसके right subtree में सबसे छोटी value, वहां से left children follow करके मिलती है) से replace करना है और फिर उस successor node को इसके बजाय delete करना, जिसमें ज़्यादा से ज़्यादा एक child होने की guarantee है।

उदाहरण: 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, और deletion मिलकर एक BST का पूरा operational toolkit बनाते हैं — तीनों tree की height के अनुपात में time में चलते हैं, यही कारण है कि उस height को छोटा रखना (एक balanced tree के ज़रिए) practice में इतना मायने रखता है।

उदाहरण: 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;
}
Related Topics

Trie में Insert और Search · Binary Search Tree क्या है · Jump Search क्या है · Ternary Search क्या है

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. insert में (संभवतः नए) node को return करना भूल जाना, इसलिए parent link update नहीं होता।
  2. दो children वाले node को इसका inorder successor copy करके और इसे delete करने के बजाय सीधे हटाकर delete करना।
  3. हटाए गए nodes को free न करना, या उन्हें free करना और फिर pointer उपयोग करना।
🔒

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.