Test by Bikram | Data Structures | Test 2 | Question: 27

Question

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?

• A. O(1)
• B. O(n log n)
• C. O(n)  
• D. O(log n)

Comments

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 

Answer 1

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