- #1
ducmod
- 86
- 0
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!