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!
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
A binary tree of level 0 has 1 node.
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
See also A000225 from the Online Encyclopedia of Integer Sequences.