# Balance Tree with depth n has how many nodes maximum?

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!

• 2^n + 2^n-1 + ... + 2^0
– user40980
Commented May 29, 2013 at 1:05
• Yea I just figured that part out, but is there a shorter way of representing that, without the "..."? Commented May 29, 2013 at 1:09
• Not without LaTeX :-) Commented May 29, 2013 at 1:36

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.