426 views

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?

1. O(1)
2. O(n log n)
3. O(n)
4. O(log n)

Sorry Bikram but I didn't got your worst case time.

@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)

yeah, now I got it right O(n)

thanks @Bikram

in worst case the tree can grow up to the height of n (skewed tree), therefore tightest upper bound is O(n)

by