Number of comparisons to find an element in a BST with 635 elements?

Question

I am a freshman in Computer Science University, so please give me a understandable justification.

I have a binary tree that is equilibrated by height which has 635 nodes. What is the number of comparisons that will occur in the worst case scenario and why?

Solution

Here's one way to think about this. Every time you do a comparison in a binary search tree, one of the following happens:

• You have walked off the tree. In this case, you're done.
• The value you're looking for matches the node you're currently exploring. In this case, you're done.
• The value you're looking for does not match the node you're exploring. In that case, you either descend to the left or descend to the right.

The key observation here is that after each step, you either terminate (yay!) or descend lower in the tree. At each point, you make one comparison. Since you can't descend forever, there are only so many comparisons that you can make - specifically, if the tree has height h, the maximum number of comparisons you can make is h + 1, which happens if you do one comparison per level.

In your question, you're given that you have a balanced binary search tree of 635 nodes. It's not 100% clear what "balanced" means in this context, since there are many different ways of determining whether a tree is balanced and they all lead to different tree heights. I'm going to assume that you are given a complete binary search tree, which is one in which all levels except the last are filled.

The reason this is important is that if you have a complete binary search tree of height h, it can have at most 2^{h + 1} - 1 nodes in it. If we try to solve for the height of the tree in terms of the number of nodes, we get this:

n = 2^h+1 - 1

n + 1 = 2^h+1

lg (n + 1) = h + 1

lg (n + 1) - 1 = h

Therefore, if you have the number of nodes n, you can determine the minimum height of a complete binary search tree holding n nodes. In your case, n = 635, so we get

lg (635 + 1) - 1 = h

lg (636) - 1 = h

9.312882955 - 1 = h

8.312882955 = h

Therefore, the tree has height 8.312882955. Of course, trees can't have fractional height, so we can take the ceiling to find that the height of the tree would be 9. Since the maximum number of comparisons made is h + 1, there are at most 10 comparisons made when doing a lookup.

Hope this helps!

Comments

[Mihai Alin]

thank you a lot, I finally understand xD (my lecturer is not able to teach us how this works) we believed that we have 635 comparisons, because you compare your data with every node.