Binary Search Tree (BST): Concept and Search Operation

Binary Search Tree (BST) ek special node-based binary tree data structure hai jo fast search, insertion, aur deletion operations provide karta hai. BST binary search ki efficiency ko dynamic linked structure ki flexibility ke saath merge karta hai.

The BST Property (Invariable Rule)

BST ke har node X ke liye:

1. X ke left subtree me jitne bhi nodes hain, unki keys strictly X->key se less than (<) honi chahiye.
2. X ke right subtree me jitne bhi nodes hain, unki keys strictly X->key se greater than (>) honi chahiye.
3. Left aur right subtrees bhi recursively valid Binary Search Trees hone chahiye.
4. Standard BST me duplicate keys allowed nahi hoti hain.

Valid BST:                   Invalid BST:
         [ 50 ]                         [ 50 ]
        /      \                       /      \
    [ 30 ]     [ 70 ]              [ 30 ]     [ 70 ]
    /   \      /    \              /   \
 [ 20] [ 40 ] [ 60] [ 80 ]      [ 20] [ 60 ] <-- INVALID! 60 > 50 in Left Subtree!

Search Operation in BST

SEARCH_BST(root, key)
1. If root == NULL or root->key == key then:
       Return root
2. If key < root->key then:
       Return SEARCH_BST(root->left, key)
3. Else:
       Return SEARCH_BST(root->right, key)

Search Complexity

• Best / Balanced Case: O(log n) time jab tree height-balanced ho (height = log2 n).
• Worst Case: O(n) jab BST skewed tree ban jaye (e.g. sorted numbers 10, 20, 30, 40 insert karne par).

Agli post me hum cover karenge Binary Search Tree (BST): Insertion and Deletion Operations (3 Cases).