I want to know what will be the time complexity to search, insert and delete an element in a) balanced binary search tree. b) unbalanced binary search tree.


closed as unclear what you're asking by fade2black, Evil, David Richerby, Yuval Filmus, cody Dec 7 '17 at 16:13

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What have you tried and where did you get stuck? Those results are utterly standard. Where did you look? $\endgroup$ – Raphael Nov 29 '17 at 10:38
  • $\begingroup$ For balanced Binary search tree this is what i think , for searching (assuming element needed is at leaf position) we would require to search upto last level , just like binary search the problem gets divided each time till we get the element therfore O(log n)..i dont know its correct or not...for unbalanced i dont know where to start... $\endgroup$ – JobLess Nov 29 '17 at 10:50
  • $\begingroup$ I suggest you pick up a text book that explains the basics and then this analysis to you. I recommend Sedgewick's books. $\endgroup$ – Raphael Nov 29 '17 at 10:54
  • $\begingroup$ This is what is writeen in the text ". The running times of algorithms on binary search trees depend on the shapes of the trees, which, in turn, depends on the order in which keys are inserted." So if shape of the tree skews either left or right then all the nodes will be present on one side only.. So suppose that element to be found is at last level ... N nodes needs to be visited hence it is O(n) is it correct $\endgroup$ – JobLess Nov 29 '17 at 12:06

Best case time complexity for search, insertion, and deletion is O(log n). This would correspond to a balanced tree.

The worst case is O(n). This would correspond to the unbalanced tree

  • $\begingroup$ You mean $\Omega(n)$. $\endgroup$ – Raphael Nov 29 '17 at 10:39

In addition to user9023727's answer, the time complexity for insert and delete is dependent on the time complexity of the search function. This is because for insert you need to find the correct position to insert, and for delete you need to find the node of the value you are deleting.


Not the answer you're looking for? Browse other questions tagged or ask your own question.