1 1 vote Could a binary search tree be built using o(n lg n) comparisons in the comparison model? Explain why or why not. Algorithms sorting algorithms time-complexity test-series + – Ravi Dubey 1.3k views answer comment Share Follow Print See all 2 Comments 2 2 Comments reply abhishekmehta4u commented Aug 2, 2018 reply Follow flag It should be O(n^2) 1 1 replyShare Rishav Kumar Singh commented Aug 2, 2018 reply Follow flag abhishekmehta4u can you explain How it should be $O(n^2)$ 1 1 replyShare Please log in or register to add a comment.
Best answer 1 1 vote NO, or else we could sort in o(n lg n) time by building a BST in o(n lg n) time and then doing an in-order tree walk in O(n) time. Rishav Kumar Singh answered Aug 2, 2018 • selected Aug 2, 2018 by Ravi Dubey Rishav Kumar Singh comment Share Follow 0 reply Please log in or register to add a comment.
1 1 vote In case of skewed BST (worst case) : O(n2) Inserting first element ; 0 comparison Inserting second element : 1 comparison Inserting nth element : n-1 comparisons Total : O(n2) comparisons In case of Balanced BST : O(nlogn) Shiv Gaur answered Aug 16, 2018 Shiv Gaur comment Share Follow 0 reply Please log in or register to add a comment.
