PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Binary Search Tree (BST): Definition, Left < Root < Right Property (बाइनरी सर्च ट्री (BST): बायां < रूट < दायां मुख्य नियम) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: A Binary Search Tree (BST) is a node-based binary tree enforcing the strict global ordering invariant: all keys in a node's left subtree are smaller than the node's key, and all keys in its right subtree are greater. Because this property holds recursively for entire subtrees—not merely immediate children—an Inorder traversal always yields keys in sorted ascending order.
अध्याय सार: बाइनरी सर्च ट्री (BST) एक ऐसी बाइनरी ट्री संरचना है जो प्रत्येक नोड पर वैश्विक नियम लागू करती है: किसी नोड के पूरे बाएं सबट्री की सभी कुंजियां (Keys) रूट से छोटी तथा पूरे दाएं सबट्री की सभी कुंजियां रूट से बड़ी होती हैं। इसी कारण BST का इनऑर्डर ट्रैवर्सल सदैव आरोही (Sorted Ascending) क्रम में होता है।
Binary Search Tree (BST): Definition, Left < Root < Right Property: Detailed Notes & Architecture (बाइनरी सर्च ट्री (BST): बायां < रूट < दायां मुख्य नियम)
1. Formal Recursive BST Ordering Invariant (औपचारिक रिकर्सिव BST क्रम नियम)
[EN] A Binary Search Tree satisfies three recursive conditions at every node x: (1) every key residing anywhere inside x's entire left subtree is strictly less than x.key; (2) every key residing anywhere inside x's entire right subtree is strictly greater than x.key (if duplicates are allowed, one side consistently uses <= or >=, or nodes keep a frequency counter); and (3) both x.left and x.right are themselves valid BSTs. This structural ordering separates search spaces cleanly at each comparison.
[HI] बाइनरी सर्च ट्री में प्रत्येक नोड x के लिए तीन नियम लागू होते हैं: (1) x के पूरे बाएं सबट्री में स्थित हर मान x से छोटा होगा; (2) x के पूरे दाएं सबट्री में स्थित हर मान x से बड़ा होगा (डुप्लीकेट होने पर <= या काउंट फ़ील्ड उपयोग होता है); तथा (3) बायां व दायां दोनों सबट्री स्वयं भी वैध BST होने चाहिए।
2. Global Subtree Rule vs Local-Only Validation Trap (वैश्विक सबट्री नियम बनाम केवल स्थानीय चाइल्ड जांच की भूल)
[EN] A classic exam error is checking only immediate children (`left->data < root->data < right->data`), which FAILS to validate a BST! For example, root 20 with right child 30 and 30's left child 15 satisfies local comparisons (20 < 30 and 15 < 30), yet violates the BST invariant because 15 lies in 20's right subtree where all values must exceed 20. True validation either propagates `(minBound, maxBound)` limits down recursion or verifies that an Inorder traversal is strictly increasing.
[HI] परीक्षा में अक्सर पूछा जाने वाला जाल यह है कि केवल तत्काल बच्चों (`left < root < right`) की जांच करना पर्याप्त नहीं है! उदाहरणार्थ, रूट 20 के राइट चाइल्ड 30 का लेफ्ट चाइल्ड 15 होने पर `15 < 30` स्थानीय रूप से सही दिखता है, पर 15 रूट 20 के दाएं सबट्री में होकर 20 से छोटा होने से BST नियम तोड़ देता है। सही जांच `(min, max)` रेंज भेजकर या इनऑर्डर को बढ़ते क्रम में जांचकर होती है।
3. Extremum Keys, Successors & Catalan Tree Count (न्यूनतम/अधिकतम कुंजी, सक्सेसर व कैटालन संख्या)
[EN] In any BST, the minimum key resides at the leftmost node (follow `left` until `left == NULL`) and the maximum key at the rightmost node (follow `right` until `right == NULL`)—both found in O(h) time. The Inorder Successor of node x (next larger key) is the minimum of `x->right` if `x->right != NULL`, or the lowest ancestor for which x sits in its left subtree. With n distinct keys, the total number of structurally distinct BSTs equals the n-th Catalan number: C_n = (2n)! / ((n+1)! * n!).
[HI] किसी भी BST में सबसे छोटा तत्व सबसे बाएं छोर पर और सबसे बड़ा तत्व सबसे दाएं छोर पर होता है, जिन्हें O(h) समय में पाया जा सकता है। n भिन्न कुंजियों से बनने वाले कुल संभावित भिन्न BST की संख्या n-वीं कैटालन संख्या (Catalan Number) `C_n = (2n)! / ((n+1)! * n!)` के बराबर होती है (जैसे n=3 पर 5 BST)।
4. BST vs Binary Heap vs Hash Table Tradeoffs (BST बनाम बाइनरी हीप बनाम हैश टेबल तुलना)
[EN] Unlike a Max/Min-Heap (which only orders parent vs direct children and cannot list keys sorted in O(n) or support O(log n) arbitrary search), a BST maintains full global ordering—enabling O(n) sorted traversal, O(h) range queries `[low, high]`, and floor/ceiling/rank queries. While Hash Tables give O(1) expected point lookups, they cannot efficiently execute range searches, prefix queries, or ordered iteration—making balanced BSTs (used in C++ `std::map`/`std::set` and SQL B-Trees) indispensable.
[HI] हीप केवल पेरेंट-चाइल्ड तुलना रखता है और किसी भी मान की खोज O(n) में करता है, जबकि BST पूर्ण क्रम बनाए रखने से सॉर्टेड लिस्ट, रेंज क्वेरी (`[low, high]`) व रैंक प्रश्नों को अत्यंत तेज बनाता है। हैश टेबल O(1) प्वाइंट सर्च तो देती है पर रेंज क्वेरी व सॉर्टेड आउटपुट नहीं दे पाती, इसलिए C++ `std::map` में संतुलित BST उपयोग होता है।
Syntax, Formula & Technical Example (Binary Search Tree (BST): Definition, Left < Root < Right Property)
// Validating BST via Global (min, max) Range Bounds (O(n) time, O(h) space)
bool isValidBST(Node* root, long minVal, long maxVal) {
if (root == NULL) return true;
if (root->data <= minVal || root->data >= maxVal) return false;
return isValidBST(root->left, minVal, root->data) &&
isValidBST(root->right, root->data, maxVal);
}
Node* findMin(Node* root) { while (root && root->left) root = root->left; return root; }
Node* findMax(Node* root) { while (root && root->right) root = root->right; return root; }
Binary Search Tree (BST): Definition, Left < Root < Right Property Quick Reference & Comparison Table
| BST Property / Concept | Formal Specification | Exam Significance |
|---|---|---|
| Left < Root < Right Rule | All left subtree keys < Root < All right subtree keys | Applies globally to entire subtrees, not just direct children |
| Inorder Traversal Property | Produces sorted ascending sequence | Used directly to validate BST or find k-th smallest |
| Minimum & Maximum Key | Leftmost node (Min) and Rightmost node (Max) | Both located in O(h) time without full scan |
| Distinct BST Count (n keys) | Catalan Number C_n = (2n)! / ((n+1)! * n!) | For n=3 -> 5 BSTs; for n=4 -> 14 BSTs |
Binary Search Tree (BST): Definition, Left < Root < Right Property Top 20 Bilingual MCQs with Answers
Q1. What is the core invariant defining a valid Binary Search Tree (BST) with distinct keys?
(भिन्न कुंजियों वाले एक वैध बाइनरी सर्च ट्री (BST) को परिभाषित करने वाला मुख्य नियम क्या है?)
(A) All leaves must reside at the exact same level
(B) Only immediate left child < node.key < immediate right child
(C) Parent key must be greater than both children
(D) Every key in a node's entire left subtree is < node.key, and every key in its entire right subtree is > node.key
Correct Answer: (D)
[EN] The ordering constraint must hold for ALL descendants in the left and right subtrees, not just direct children.
[HI] यह नियम केवल सीधे बच्चों पर नहीं बल्कि पूरे बाएं और पूरे दाएं सबट्री के प्रत्येक नोड पर लागू होता है।
Q2. A binary tree has root 15, left child 10, right child 25, and 25 has left child 12. Is this a valid BST?
(एक ट्री का रूट 15 है, लेफ्ट चाइल्ड 10, राइट चाइल्ड 25 है, तथा 25 का लेफ्ट चाइल्ड 12 है। क्या यह वैध BST है?)
(A) Yes — because all leaves are balanced
(B) No — 12 sits in the right subtree of 15 but is less than 15
(C) No — only because 12 is an even number
(D) Yes — because 10 < 15 < 25 and 12 < 25
Correct Answer: (B)
[EN] Even though 12 < 25 locally, 12 lies inside 15's right subtree where every key must exceed 15.
[HI] भले ही 12 < 25 स्थानीय रूप से सही है, पर 12 रूट 15 के दाएं सबट्री में होकर 15 से छोटा है—अतः यह अवैध BST है।
Q3. Which traversal of a Binary Search Tree ALWAYS outputs its elements in sorted ascending order?
(बाइनरी सर्च ट्री (BST) का कौन सा ट्रैवर्सल सदैव तत्वों को बढ़ते हुए सॉर्टेड क्रम में प्रिंट करता है?)
(A) Inorder Traversal (L-N-R)
(B) Preorder Traversal (N-L-R)
(C) Postorder Traversal (L-R-N)
(D) Level Order Traversal (BFS)
Correct Answer: (A)
[EN] Visiting Left (< Root), then Root, then Right (> Root) naturally produces ascending order.
[HI] पहले छोटे (Left), फिर बीच के (Root), फिर बड़े (Right) मान विज़िट होने से सदैव आरोही क्रम मिलता है।
Q4. Where is the smallest (minimum) key guaranteed to be located in any non-empty BST?
(किसी भी गैर-खाली BST में सबसे छोटी (Minimum) कुंजी कहाँ स्थित होना सुनिश्चित है?)
(A) Always at a leaf with depth h
(B) At the rightmost node
(C) At the root node
(D) At the leftmost node (follow left pointers until left == NULL)
Correct Answer: (D)
[EN] Smallest values branch strictly left until no left child exists; note that the minimum node can still have a right child!
[HI] सबसे बायां नोड (जहां `left == NULL` हो) सदैव न्यूनतम कुंजी रखता है (भले ही उसका राइट चाइल्ड मौजूद हो)।
Q5. How many structurally distinct Binary Search Trees can be formed using n = 4 distinct keys (e.g., 1, 2, 3, 4)?
(n = 4 भिन्न कुंजियों (जैसे 1, 2, 3, 4) से संरचनात्मक रूप से कुल कितने अलग-अलग BST बनाए जा सकते हैं?)
(A) 5
(B) 42
(C) 16
(D) 14
Correct Answer: (D)
[EN] Catalan number C_4 = (8!) / (5! * 4!) = 14 distinct BSTs.
[HI] कैटालन सूत्र C_4 = (2*4)! / (5! * 4!) = 14 अलग-अलग BST बनते हैं।
Q6. What is the minimum possible height (in edges) of a BST containing n = 15 distinct keys?
(n = 15 भिन्न कुंजियों वाले BST की न्यूनतम संभव ऊंचाई (Edges में) कितनी हो सकती है?)
(A) 14
(B) 3
(C) 7
(D) 4
Correct Answer: (B)
[EN] Minimum height occurs when balanced/perfect: h = floor(log2(15)) = 3 (holding 2^4 - 1 = 15 nodes across levels 0..3).
[HI] 15 नोड्स पूर्णतः संतुलित होने पर 4 स्तरों (स्तर 0 से 3) में समा जाते हैं, अतः न्यूनतम ऊंचाई 3 edges होगी।
Q7. Suppose a BST node x has NO right child (x->right == NULL). Where is x's Inorder Successor located?
(यदि किसी BST नोड x का कोई दायां चाइल्ड न हो (x->right == NULL), तो उसका इनऑर्डर सक्सेसर कहाँ होता है?)
(A) x's immediate right sibling
(B) Always the global root
(C) The lowest ancestor of x whose left child is also an ancestor of x
(D) The rightmost node of x's left subtree
Correct Answer: (C)
[EN] Moving up parent links until stepping up from a left-child branch reaches the first ancestor greater than x.
[HI] पेरेंट की ओर ऊपर चलते समय वह पहला पूर्वज नोड जिसके बाएं सबट्री में x स्थित हो, वही x का इनऑर्डर सक्सेसर होता है।
Q8. If a node x in a BST has BOTH left and right non-empty subtrees, its Inorder Predecessor is:
(यदि BST के किसी नोड x के बाएं और दाएं दोनों सबट्री मौजूद हों, तो उसका इनऑर्डर प्रीडीसेसर (Predecessor) कौन होगा?)
(A) x's immediate left child always
(B) x's parent node
(C) The maximum (rightmost) node in x's left subtree
(D) The minimum (leftmost) node in x's right subtree
Correct Answer: (C)
[EN] Inorder predecessor is the largest key strictly smaller than x—the rightmost node inside x->left.
[HI] x से ठीक छोटी कुंजी x के बाएं सबट्री का सबसे बड़ा (सबसे दाहिना) नोड होता है।
Q9. How does a BST structurally differ from a Binary Max-Heap?
(एक बाइनरी सर्च ट्री (BST) और बाइनरी मैक्स-हीप में मुख्य संरचनात्मक अंतर क्या है?)
(A) Max-Heap finds arbitrary keys in O(log n)
(B) Max-Heap sorts all keys in Inorder; BST does not
(C) BST enforces Left < Root < Right globally; Max-Heap only requires Parent >= Children and must be a CBT
(D) BST must always be a Complete Binary Tree; Max-Heap need not be
Correct Answer: (C)
[EN] Heaps impose vertical parent-child priority only and enforce CBT shape, whereas BST imposes horizontal left/right ordering.
[HI] BST बाएं < रूट < दाएं का क्षैतिज क्रम रखता है, जबकि मैक्स-हीप केवल पेरेंट >= चाइल्ड का ऊर्ध्वाधर क्रम व CBT आकार रखता है।
Q10. Which condition confirms that a binary tree is a valid BST using an O(n) Inorder traversal?
(O(n) इनऑर्डर ट्रैवर्सल का उपयोग करके किसी बाइनरी ट्री के वैध BST होने की पुष्टि कैसे होती है?)
(A) First and last visited keys are equal
(B) Every visited key is strictly greater than the previously visited key (`prev < curr`)
(C) Total nodes visited are odd
(D) Keys appear in descending order
Correct Answer: (B)
[EN] Instead of allocating an O(n) array, keeping a single `prev` pointer confirms monotonic ascending order in O(h) space.
[HI] एक `prev` मान रखकर जांचते हैं कि इनऑर्डर में प्रत्येक अगला मान पिछले से बड़ा (`prev < curr`) आ रहा है या नहीं।
Q11. Which standard library container in C++ STL and Java Collections is typically implemented using a self-balancing BST (Red-Black Tree)?
(C++ STL और Java में कौन से मानक कंटेनर सामान्यतः सेल्फ-बैलेंसिंग BST (रेड-ब्लैक ट्री) द्वारा बनाए जाते हैं?)
(A) std::priority_queue and Java PriorityQueue
(B) C++ std::map / std::set and Java TreeMap / TreeSet
(C) C++ std::unordered_map and Java HashMap
(D) std::vector and ArrayList
Correct Answer: (B)
[EN] Ordered associative maps/sets require O(log n) lookup plus sorted iteration—implemented via Red-Black Trees.
[HI] क्रमबद्ध कुंजियों और O(log n) सर्च के लिए `std::map`/`std::set` तथा `TreeMap`/`TreeSet` रेड-ब्लैक ट्री (BST) उपयोग करते हैं।
Q12. What is the maximum number of nodes a BST can have if its height is h (edges)?
(यदि किसी BST की ऊंचाई h (Edges में) है, तो उसमें अधिकतम कितने नोड्स हो सकते हैं?)
(A) 2^(h+1) - 1
(B) 2^h - 1
(C) h + 1
(D) 2^h
Correct Answer: (A)
[EN] Just like any binary tree, packing every level 0..h completely yields 2^(h+1) - 1 nodes.
[HI] किसी भी बाइनरी ट्री की भांति सभी स्तर 0..h पूर्णतः भरने पर अधिकतम 2^(h+1) - 1 नोड्स हो सकते हैं।
Q13. Which Level Order sequence CANNOT represent any valid Binary Search Tree (BST)?
(निम्नलिखित में से कौन सा लेवल ऑर्डर अनुक्रम किसी भी वैध बाइनरी सर्च ट्री (BST) को नहीं दर्शा सकता?)
(A) [10, 5, 20]
(B) [10, 20, 30]
(C) [10, 20, 5]
(D) [20, 10, 30]
Correct Answer: (C)
[EN] With root 10, 20 (> 10) cannot be its left child; even if 20 is right child of 10 at level 1, 5 (< 10) cannot sit in 20's subtree at level 2.
[HI] रूट 10 होने पर 20 बायां चाइल्ड नहीं हो सकता, और यदि 20 स्तर 1 पर दायां चाइल्ड हो तो 5 (< 10) स्तर 2 में 20 के सबट्री में नहीं आ सकता।
Q14. Which statement is NOT true about a Binary Search Tree (BST)?
(बाइनरी सर्च ट्री (BST) के संबंध में इनमें से कौन सा कथन असत्य (NOT true) है?)
(A) Every Binary Search Tree is automatically height-balanced with height O(log n)
(B) Inorder traversal gives keys in sorted order
(C) Range queries [L, R] can be answered efficiently by pruning out-of-range subtrees
(D) The minimum node of a BST can never have a left child
Correct Answer: (A)
[EN] A standard BST does NOT self-balance; sorted insertions produce height n - 1 (O(n)).
[HI] सामान्य BST स्वतः संतुलित नहीं होता; सॉर्टेड इनपुट से इसकी ऊंचाई O(n) तक जा सकती है।
Q15. Which value in a BST can have a non-NULL right child while still being the overall Minimum key of the tree?
(BST में वह कौन सा नोड है जो पूरे ट्री की सबसे छोटी (Minimum) कुंजी होने के बावजूद अपने पास एक नॉन-NULL राइट चाइल्ड रख सकता है?)
(A) The leftmost node (minimum node) — any node in its right subtree is > minimum and < its parent
(B) No minimum node can have any child
(C) The root only if it has 2 children
(D) The global maximum node
Correct Answer: (A)
[EN] The minimum node has `left == NULL`, yet it CAN have a right child (keys strictly between `min` and `min`'s parent).
[HI] सबसे बायां (न्यूनतम) नोड `left == NULL` रखता है, पर उसका राइट सबट्री मौजूद हो सकता है जिसमें उससे बड़े पर उसके पेरेंट से छोटे मान होंगे।
Q16. If keys 10, 5, 15, 3, 7, 12, 20 form a BST, which pair of keys are the Inorder Predecessor and Inorder Successor of 10?
(10, 5, 15, 3, 7, 12, 20 से बने BST में रूट 10 के इनऑर्डर प्रीडीसेसर व इनऑर्डर सक्सेसर क्रमशः कौन से हैं?)
(A) 3 and 20
(B) 5 and 12
(C) 7 and 12
(D) 5 and 15
Correct Answer: (C)
[EN] Inorder sequence is [3, 5, 7, 10, 12, 15, 20]. Immediately before 10 is 7 (max of left subtree); right after 10 is 12 (min of right subtree).
[HI] इनऑर्डर क्रम [3, 5, 7, 10, 12, 15, 20] है; 10 के ठीक पहले 7 (प्रीडीसेसर) और ठीक बाद 12 (सक्सेसर) आता है।
Q17. Within Binary Search Tree (BST): Definition, Left < Root < Right Property, which bst property / concept directly maps to: "All left subtree keys < Root < All right subtree keys"?
(Binary Search Tree (BST): Definition, Left < Root < Right Property में कौन सा BST Property / Concept सीधे "All left subtree keys < Root < All right subtree keys" से संबंधित है?)
(A) Left < Root < Right Rule
(B) Inorder Traversal Property
(C) Distinct BST Count (n keys)
(D) Minimum & Maximum Key
Correct Answer: (A)
[EN] In Binary Search Tree (BST): Definition, Left < Root < Right Property, 'Left < Root < Right Rule' handles 'All left subtree keys < Root < All right subtree keys' (Applies globally to entire subtrees, not just direct children).
[HI] Binary Search Tree (BST): Definition, Left < Root < Right Property में 'Left < Root < Right Rule' का कार्य/विवरण 'All left subtree keys < Root < All right subtree keys' (Applies globally to entire subtrees, not just direct children) है।
Q18. Which option accurately describes 'Inorder Traversal Property' in Binary Search Tree (BST): Definition, Left < Root < Right Property?
(Binary Search Tree (BST): Definition, Left < Root < Right Property के संदर्भ में 'Inorder Traversal Property' की सही विशेषता कौन सी है?)
(A) Leftmost node (Min) and Rightmost node (Max)
(B) Catalan Number C_n = (2n)! / ((n+1)! * n!)
(C) Produces sorted ascending sequence
(D) All left subtree keys < Root < All right subtree keys
Correct Answer: (C)
[EN] 'Inorder Traversal Property' provides 'Produces sorted ascending sequence' — key point: Used directly to validate BST or find k-th smallest.
[HI] 'Inorder Traversal Property' का मुख्य विवरण 'Produces sorted ascending sequence' है (Used directly to validate BST or find k-th smallest)।
Q19. In Binary Search Tree (BST): Definition, Left < Root < Right Property, identify the correct parameter for the specification: "Leftmost node (Min) and Rightmost node (Max)".
(Binary Search Tree (BST): Definition, Left < Root < Right Property में "Leftmost node (Min) and Rightmost node (Max)" विवरण किस विकल्प के लिए सही है?)
(A) Inorder Traversal Property
(B) Left < Root < Right Rule
(C) Minimum & Maximum Key
(D) Distinct BST Count (n keys)
Correct Answer: (C)
[EN] 'Minimum & Maximum Key' corresponds to 'Leftmost node (Min) and Rightmost node (Max)' (Both located in O(h) time without full scan).
[HI] 'Minimum & Maximum Key' का संबंध 'Leftmost node (Min) and Rightmost node (Max)' (Both located in O(h) time without full scan) से है।
Q20. Considering Binary Search Tree (BST): Definition, Left < Root < Right Property, what key behavior defines 'Distinct BST Count (n keys)'?
(Binary Search Tree (BST): Definition, Left < Root < Right Property में 'Distinct BST Count (n keys)' की मुख्य भूमिका या मान क्या है?)
(A) All left subtree keys < Root < All right subtree keys
(B) Produces sorted ascending sequence
(C) Catalan Number C_n = (2n)! / ((n+1)! * n!)
(D) Leftmost node (Min) and Rightmost node (Max)
Correct Answer: (C)
[EN] 'Distinct BST Count (n keys)' represents 'Catalan Number C_n = (2n)! / ((n+1)! * n!)' (For n=3 -> 5 BSTs; for n=4 -> 14 BSTs).
[HI] 'Distinct BST Count (n keys)' का अर्थ/मान 'Catalan Number C_n = (2n)! / ((n+1)! * n!)' है (For n=3 -> 5 BSTs; for n=4 -> 14 BSTs)।
Binary Search Tree (BST): Definition, Left < Root < Right Property — Exam FAQs
Q1: Why isn't checking `node->left->data < node->data && node->data < node->right->data` enough to check if a tree is a BST?
केवल `left < root < right` जांचने से कोई बाइनरी ट्री BST क्यों साबित नहीं होता?
[EN] Because a descendant deeper inside the right subtree could still be smaller than the root (or one deeper in the left subtree larger than the root) while still satisfying its immediate parent's condition. You must enforce `(min, max)` bounds down the whole tree.
[HI] क्योंकि दाएं सबट्री में गहराई पर बैठा कोई नोड अपने सीधे पेरेंट से तो छोटा हो सकता है, पर मुख्य रूट से भी छोटा निकलकर BST नियम तोड़ सकता है। इसलिए पूरे मार्ग पर `(min, max)` सीमा जांचनी पड़ती है।
Q2: Can a Binary Search Tree store duplicate keys?
क्या बाइनरी सर्च ट्री (BST) में डुप्लीकेट कुंजियां (Duplicate keys) रखी जा सकती हैं?
[EN] By strict textbook definition all keys are distinct, or if duplicates occur in practice, implementations either attach a `count` integer to each node or adopt a consistent convention such as placing duplicates in the right subtree (`>=`).
[HI] शुद्ध परिभाषा में कुंजियां भिन्न होती हैं, पर व्यावहारिक रूप से डुप्लीकेट रखने के लिए या तो नोड में `count` फ़ील्ड जोड़ा जाता है या नियम बनाकर समान मानों को दाएं (या बाएं) सबट्री में भेजा जाता है।
Q3: Why is a BST preferred over a sorted array for dynamic datasets?
बदलते (Dynamic) डेटा के लिए सॉर्टेड एरे की जगह BST को क्यों चुना जाता है?
[EN] While both support O(log n) search (when BST is balanced), inserting or deleting in a sorted array requires O(n) element shifting, whereas a balanced BST inserts and deletes in O(log n) time.
[HI] सॉर्टेड एरे में सर्च तो O(log n) है पर नया तत्व डालने या हटाने पर तत्व खिसकाने में O(n) समय लगता है, जबकि संतुलित BST में तीनों कार्य O(log n) में हो जाते हैं।
Post a Comment
Post a Comment