Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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!

share|improve this question
    
2^n + 2^n-1 + ... + 2^0 –  MichaelT May 29 '13 at 1:05
    
Yea I just figured that part out, but is there a shorter way of representing that, without the "..."? –  floatfil May 29 '13 at 1:09
    
Not without LaTeX :-) –  Jörg W Mittag May 29 '13 at 1:36

1 Answer 1

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 enter image description here

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.