Comparsion done at Level i on a tree

[Gear2d]

In class we had done and average case of a decision tree, and I am confused as to have at Level i you would have 2i + 1 comparison. How do we arrive at this?

I see at level 0 you have 1 node so 2(0) + 1 = 1 comparison

Level 1 with 1 node you have 2(1) +1 = 3 comparisons

Level 2 with 4 nodes you have 2(2) + 1 = 5 comparisons

Level 3 with 8 nodes (2^3) you have 2(3) + 1 = 7 comparisons

Level 4 with 16 nodes you have 2(4) + 1 = 9 comparisons

I am not seeing the connection between the number of nodes and number of comparisons.

 

[Valkarie]

The connection is a result of the structure of a decision tree. Every node at level i has two branches which are each compared to a condition before being used to select the next node. Thus, for a given level i, there are 2i comparisons that need to be made in order to reach the leaf nodes. The +1 is added to account for the comparison that needs to be made at the root node. So the total number of comparisons at level i is 2i + 1.