Question:
What is the worst-case time complexity of searching for an element in a Binary Search Tree (BST)?
एक बाइनरी सर्च ट्री (BST) में किसी तत्व को खोजने की सबसे खराब स्थिति (वबस्ट-केस) समय जटिलता क्या है?
Options:
- \(O(n)\)
- \(O(\log n)\)
- \(O(n \log n)\)
- \(O(1)\)
- \(O(n)\)
- \(O(\log n)\)
- \(O(n \log n)\)
- \(O(1)\)
Correct Answer: a)
Explanation:
When a BST is skewed (degenerate tree, like a linked list where elements were inserted in sorted order), the height becomes \(n\), leading to a worst-case search time of **\(O(n)\)** (Option a).
जब BST तिरछा (Skewed) हो जाता है, तो उसकी ऊँचाई \(n\) हो जाती है, जिससे वर्स्ट-केस सर्च समय **\(O(n)\)** होता है (विकल्प a)।