1 votes 1 votes 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 asked Aug 2, 2018 Ravi Dubey 858 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply abhishekmehta4u commented Aug 2, 2018 reply Follow Share It should be O(n^2) 1 votes 1 votes Rishav Kumar Singh commented Aug 2, 2018 reply Follow Share abhishekmehta4u can you explain How it should be $O(n^2)$ 1 votes 1 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes 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 See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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 See all 0 reply Please log in or register to add a comment.
