2 votes 2 votes Which one of the following is the tightest upper bound that represents the time complexity of inserting an element into a binary search tree of n nodes? O(1) O(n log n) O(n) O(log n) DS tbb-ds-2 + – Bikram asked Nov 26, 2016 edited Jul 20, 2017 by Bikram Bikram 687 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments SKP commented Jul 20, 2017 reply Follow Share Sorry Bikram but I didn't got your worst case time. 0 votes 0 votes Bikram commented Jul 21, 2017 reply Follow Share @skp To insert an element, we need to search for its place first. The search operation may take O(n) for a skewed tree like following. To insert 60, we will have to traverse all nodes. 20 \ 30 \ 40 \ 50 after finding 50 from top to bottom we can insert 60 only in this tree .. so worst case time it takes O(n) 2 votes 2 votes SKP commented Jul 22, 2017 reply Follow Share yeah, now I got it right O(n) thanks @Bikram 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes in worst case the tree can grow up to the height of n (skewed tree), therefore tightest upper bound is O(n) Bikram answered Jul 21, 2017 Bikram comment Share Follow See all 0 reply Please log in or register to add a comment.