• Register
+2 votes

Problem :

Currently I am preparing for interview and I am stuck with one doubt related to binary tree as below

“The time required in best case for search operation in binary tree is”

Can somebody solve my doubt related to binary tree?

ago by (1.5k points)  

1 Answer

+2 votes

Solution :

I was going through the long list of questions and after reading your question I came to know that you are preparing for some interview so I am trying to answer it for you.

The time taken by balanced binary tree search tree for worst case, best case and average case is as below:

For Worst case lookup the time taken is O(log n).

For Best case lookup the time taken is O(1).

For Average case lookup the time taken is O(log n).

The worst case look up in the binary tree is the most exciting and also it is very easily observed by recognizing its first level of the binary tree which has just one node and the second has only two nodes and the third one has only four nodes and so on like this. So we can say that the number of nodes in the binary tree for depth n is exactly 2^n - 1.

ago by (2.3k points)