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?
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.
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)
in worst case the tree can grow up to the height of n (skewed tree), therefore tightest upper bound is O(n)