16
$\begingroup$

I am confused with this statement

The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$, $k \geq1$.

How come this is true. Lets say I have the following tree

    1    / \   2   3 

Here the depth of the tree is 1. So according to the formula, it will be $2^1-1 = 1$. But we have $3$ nodes here. I am really confused with this depth thing.

Any clarifications?

  • 1
    Even simpler: A binary tree with depth 0 has 1 node (the root), not 0 nodes. But check your source's definitions. If they define depth as the number of _nodes_ on the longest root-to-leaf path, instead of the (more standard) number of _edges_ on the longest root-to-leaf path, then their statement is correct.2012-05-06
  • 0
    @rajansthapit what is the name of tile/author of the book? Gadi has the correct answer.2012-05-06
  • 1
    4k+ views and not a single upvote? Time to change that! :D2013-11-12
  • 0
    Number of **internal nodes in a perfect** binary tree of depth $k$ is $2^k-1$, $k \geq1$ . You may have read it wrong. I can prove it to you but I can not create an answer because of low rep.2017-11-08

5 Answers 5