I couldn't find the answer anywhere, but let's say we have a B-Tree with min = 1 and max = 2: What is the formula to calculate the maximum number of nodes in this B-Tree if the depth is say 100? This question was given on an in-class test to which most everyone had no idea what the answer was. I was completely stumped and am wondering if anyone knows what it is. Thanks a lot!
3
-
2^n + 2^n-1 + ... + 2^0– user40980Commented May 29, 2013 at 1:05
-
Yea I just figured that part out, but is there a shorter way of representing that, without the "..."?– floatfilCommented May 29, 2013 at 1:09
-
Not without LaTeX :-)– Jörg W MittagCommented May 29, 2013 at 1:36
Add a comment
|
1 Answer
A binary tree of level 0 has 1 node.
A binary tree of level 1 has 3 nodes. (1 + 2)
A binary tree of level 2 has 7 nodes. (1 + 2 + 4)
This can be written as 2n + 2n-1 + ... + 20. In a more formal notation this can be represented as 
This also has another property that is obvious when written in binary
0 -> 1 -> 1 1 -> 3 (1 + 2) -> 11 2 -> 7 (1 + 2 + 4) -> 111 3 -> 15 (1 + 2 + 4 + 8) -> 1111
The nuber of nodes of a binary tree depth n is 2n+1 - 1.
See also A000225 from the Online Encyclopedia of Integer Sequences.