Binary search tree, number of nodes formula

[ducmod]

Homework Statement

Hello!
Typical binary search tree has a number of nodes equal to 2^(n+1) - 1.
I don't understand why we add 1 to the n?
For example: a tree has a height 4.
#
# #
# # # #
# # # # # # # #
each level has 2^i nodes; i = 0, 2^0 = 1 for the first row, etc.
If the height is 4 then total amount of nodes is 15, which is 2^4 - 1,
and not 2^(4+1) - 1.

I would be grateful for your help!

 

[Ray Vickson]

Homework Statement

Hello!
Typical binary search tree has a number of nodes equal to 2^(n+1) - 1.
I don't understand why we add 1 to the n?
For example: a tree has a height 4.
#
# #
# # # #
# # # # # # # #
each level has 2^i nodes; i = 0, 2^0 = 1 for the first row, etc.
If the height is 4 then total amount of nodes is 15, which is 2^4 - 1,
and not 2^(4+1) - 1.

I would be grateful for your help!

The formula works perfectly well if you regard the depth as n=3, rather than n=4. Four is the number of nodes in a path from root to tip, but three is the number of "steps". It is the same as saying that your first year of life has two endpoints, t = 0 and t = 1, but it is still just one year.

 

[ducmod]

The formula works perfectly well if you regard the depth as n=3, rather than n=4. Four is the number of nodes in a path from root to tip, but three is the number of "steps". It is the same as saying that your first year of life has two endpoints, t = 0 and t = 1, but it is still just one year.

I see now. Thank you!