Question

Given a binary tree with n nodes how long does it take in the worst case

Answer 1

On average, binary search trees with n nodes have O(log n) height. However, in the worst case, binary search trees can have O(n) height, when the unbalanced tree resembles a linked list (degenerate tree).

Answer 2

Given a binary tree with n nodes complexity it take in the worst case is:

• For searching, for assumption if you are breadth first traversal in a binary tree then the worst case complexity is O(n).
• For deletion, initially  you have to traverse the element and you should delete it , complexity is O(n).
• For insertion, first you should find where to place for that you need to traverse all elements, complexity is O(n).