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

Binary Search Tree क्या है

एक binary search tree एक family tree जैसा है एक rule के साथ: छोटी values left जाती हैं और बड़ी values right जाती हैं, जो किसी को ढूंढना तेज़ बनाता है।

In this page:

  1. BST Rule
  2. BST Search Idea
  3. BST Inorder
  4. BST Minimum and Maximum
  5. BST Practice
Syntax
markup 
def search(node, key):
    if node is None or node.value == key:
        return node
    if key < node.value:
        return search(node.left, key)
    return search(node.right, key)

BST Rule

एक binary search tree (BST) एक ordering rule वाली एक binary tree है: हर node के लिए, इसके left subtree में सभी values node की value से छोटी हैं, और इसके right subtree में सभी values बड़ी हैं। यही rule है जो fast searching possible बनाता है।

उदाहरण: BST Rule

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

root = Node(5)
root.left = Node(3); root.right = Node(8)
print(f"left({root.left.val}) < root({root.val}) < right({root.right.val})")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("left(%d) < root(%d) < right(%d)\n", root.left->val, root.val, root.right->val);
    return 0;
}

BST Search Idea

Ordering rule के कारण, एक BST search करने के लिए सिर्फ root से एक path follow करना चाहिए: हर node पर, target को current value से compare करें और accordingly left या right move करें, दूसरे subtree को बिना जांचे पूरी तरह discard करते हुए।

उदाहरण: BST Search Idea

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* search(Node* n, int target) {
    if (!n || n->val == target) return n;
    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};
    Node* found = search(&root, 3);
    cout << (found ? "Found" : "Not found") << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node search(Node n, int target) {
        if (n == null || n.val == target) return n;
        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);
        Node found = search(root, 3);
        System.out.println(found != null ? "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 or n.val == target:
        return n
    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, 3) else "Not found")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* search(struct Node* n, int target) {
    if (!n || n->val == target) return n;
    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};
    struct Node* found = search(&root, 3);
    printf("%s\n", found ? "Found" : "Not found");
    return 0;
}

BST Inorder

एक BST पर एक inorder traversal चलाना — left subtree, node, right subtree — हर value को पूरी तरह sorted order में visit करता है, जो BST ordering rule का सीधा परिणाम है और structure का सबसे उपयोगी properties में से एक है।

उदाहरण: BST Inorder

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

def inorder(n):
    if n is None: return
    inorder(n.left); print(n.val, end=" "); inorder(n.right)

root = Node(5)
root.left = Node(3); root.right = Node(8)
inorder(root)
print("(sorted order)")
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
void inorder(struct Node* n) { if(!n) return; inorder(n->left); printf("%d ",n->val); inorder(n->right); }
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    inorder(&root);
    printf("(sorted order)\n");
    return 0;
}

BST Minimum and Maximum

BST में minimum value हमेशा root से जितना संभव हो left children follow करके मिलती है, और maximum हमेशा जितना संभव हो right children follow करके मिलता है — node values के खिलाफ किसी comparisons की ज़रूरत भी नहीं।

उदाहरण: BST Minimum and Maximum

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* findMin(Node* n) { while (n->left) n = n->left; return n; }
Node* findMax(Node* n) { while (n->right) n = n->right; return n; }
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "Min: " << findMin(&root)->val << ", Max: " << findMax(&root)->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; }
    static Node findMax(Node n) { while (n.right != null) n = n.right; return n; }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("Min: " + findMin(root).val + ", Max: " + findMax(root).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

def find_max(n):
    while n.right: n = n.right
    return n

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("Min:", find_min(root).val, ", Max:", find_max(root).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; }
struct Node* findMax(struct Node* n) { while (n->right) n = n->right; return n; }
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("Min: %d, Max: %d\n", findMin(&root)->val, findMax(&root)->val);
    return 0;
}

BST Practice

BSTs तब सही choice हैं जब आपको fast lookups और sorted order में data retrieve करने की क्षमता दोनों चाहिए — tradeoff यह है कि एक poorly balanced BST (उदाहरण के लिए already-sorted input से बनाई गई) worst case में एक plain linked list की ओर degrade होती है।

उदाहरण: BST 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 << "Balanced BST height: " << height(&root) << 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("Balanced BST height: " + height(root));
    }
}
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("Balanced BST height:", height(root))
#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("Balanced BST height: %d\n", height(&root));
    return 0;
}
Related Topics

Binary Tree परिचय · Answer पर Binary Search · Binary Search क्या है · BST में Insert, Delete और 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. Validate करते समय किसी node को सिर्फ इसके direct children से compare करना, इसके subtree में हर node के बजाय।
  2. किसी rule के बिना duplicates handle करना, इसलिए वे दोनों sides पर end होती हैं।
  3. एक path follow करने के बजाय पूरा tree search करना, जो O(h) speed खो देता है।
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Level Order Traversal BFS Next Lesson → BST Insert Delete Search

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.