# The time required in best case for search operation in binary tree is?

406 views

## 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?

## 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.

## Related questions

4 views
Problem: I used Google to try to find a solution on the web of the above question, But I got no useful hints. Can I get Pointer information about my problem with this?
15 views
Question: How to check if a binary tree is a binary search tree?
6 views
Problem: Please help me telling a function so that I can check if a binary search tree is balanced or not.
7 views
Question: This has already been discussed here, but I have an implementation below (which was never discussed in the thread), public boolean isBalanced(BSTNode node) { if(maxHeight() > (int)(Math.log(size())/Math.log(2)) + 1) return false; else return true; } where ... tree. Basically I am checking if maxHeight > log(n), where n is the number of elements in the tree. Is this a correct solution?
3 views
Problem: Today I had an interview where I was asked to write a program which takes a Binary Tree and returns true if it is also a Binary Search Tree otherwise false. My Approach1: Perform an in-order traversal and store the elements in O(n) time. Now scan through ... BSTs. But this is going to be complicated and running time doesn't seem to be good. Please help if you know any optimal solution.
5 views
Problem: I have to pick out which operations have a better worst case time complexity on an AVL tree than a BST. I have established that the time complexity for each operation is the same depending on the tree... The worst case time complexity for an AVL tree is... Insert - O(log ... . Insert - O(height) Remove - O(height) Search - O(height) So is O(log(n)) a better time complexity than O(height)?
7 views
Problem: I used Google to try to find a solution on the web of the above question, But I got no useful hints. Can I get Pointer information about my problem with this?