• Register
2 votes
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?

8 5 2
3,230 points

Please log in or register to answer this question.

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.

8 4 1
5,680 points

Related questions

0 votes
1 answer 4 views
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?
asked Mar 31 jamuna1 30.2k points
0 votes
1 answer 15 views
15 views
Question: How to check if a binary tree is a binary search tree?
asked Apr 18 munim01 21k points
0 votes
1 answer 6 views
6 views
Problem: Please help me telling a function so that I can check if a binary search tree is balanced or not.
asked Apr 15 anika11 32.2k points
0 votes
1 answer 7 views
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?
asked Apr 15 munim01 21k points
0 votes
1 answer 3 views
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.
asked Apr 9 munim01 21k points
0 votes
1 answer 5 views
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)?
asked Apr 24 Humaira ahmed 50.7k points
0 votes
1 answer 7 views
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?
asked Mar 22 sadi1982 36.3k points
0 votes
1 answer 30 views
30 views
Problem: How do you delete a node in a binary tree in Java? How do you delete a node in a binary search tree? How many cases does it take to remove a node from a binary search tree? What is binary search tree insertion and deletion in BST? We have discussed BST search and insert operations. In this post, delete operation is discussed. When we delete a node, three possibilities arise.
asked Dec 5, 2020 Mashhoodch 13k points
0 votes
1 answer 3 views
3 views
Problem: Given a binary tree, I have to write a program to convert it to a doubly linked list. Can anyone help in explaining the recursive approach should be used?
asked Apr 16 muktaa 34.6k points
0 votes
1 answer 4 views
4 views
Problem: Is it possible for a binary search tree to have duplicates?
asked Apr 15 jamuna1 30.2k points