1 votes 1 votes some random numbers are given and asked to construct a balanced BST..what will be the time complexity? numbers in sorted order are given and asked to construct a balanced BST...what will be the time complexity?? DS data-structures binary-search-tree time-complexity + – A_i_$_h asked Jul 25, 2017 • recategorized Jul 6, 2022 by Lakshman Bhaiya A_i_$_h 295 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes I think, a. O(n^2) b. O(nlogn) Manu Thakur answered Jul 25, 2017 Manu Thakur comment Share Follow See all 3 Comments See all 3 3 Comments reply A_i_$_h commented Jul 25, 2017 reply Follow Share O(n^2) should be for the second case right?? ascending or descending then it forms a skew tree therefore O(n^2) and a small change in the question...its balanced BST not BST 0 votes 0 votes Manu Thakur commented Jul 25, 2017 i edited Jul 25, 2017 reply Follow Share I can choose middle key as root of bst and then can recursively call a function on left and right sub parts. so it will be a balanced Binary Search Tree at the end, 1 votes 1 votes A_i_$_h commented Jul 25, 2017 reply Follow Share am concerned with the time complexity for this procedure its O(n log n) i cannot understand how 0 votes 0 votes Please log in or register to add a comment.