1. How many binary nodes does a binary tree with 100 leaves have?

---

Request for Question Clarification by answerguru-ga on 17 Nov 2002 15:44 PST

Hi math01,

The only way you can know this for sure is if this is a FULL binary
tree..can I make this assumption?

Thanks,
answerguru-ga

Hello Math01,

The short answer is 99. This is because the number of internal nodes
is always one less than the number of external nodes (leaves).

There is a pretty comprehensive reference on this (including proofs
and lemmas) at:
  http://www.cs.unb.ca/courses/cs3913/BinTrees.pdf
or a HTML version in the Google cache at
http://216.239.53.100/search?q=cache:yigzd4sSk70C:www.cs.unb.ca/courses/cs3913/BinTrees.pdf+number+of+nodes+in+a+binary+tree&hl=en&ie=UTF-8
which shows the inductive proof for this 

Search terms for this kind of information includes
  number of nodes in a binary tree

--Maniac