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

Dark Mode

1 vote

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)

@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