binary trees

[Amr.Mohammad87]

I've read the following statement and I cannot understand something within it "In all binary trees, there are at most 2^i nodes at level i + 1" what I cannot understand is that tree's levels start at level 0, however, if we apply what is written in this statement there will be no level 0 at all as it says level i + 1 which mean 0 + 1 = level 1, 1 + 1 = level 2, etc. So is this statement wrong?!!! or I am missing something?!!!

[JamesCherrill]

To me it looks like that formula is OK if you number the levels starting a 1, not 0

i       level       max entries
0         1            2^0 = 1
1         2            2^1 = 2
2         3            2^2 = 4

[Amr.Mohammad87]

"The root of the tree, therefore, is at level 0" that is what is mentioned in every data structure book so I cannot start the level at 1 as all the books saying it starts at 0.

[JamesCherrill]

Where exactly did you see the text you quoted in your first post? I agree that it is normal to number the levels starting at 0, but that formula gives a maximum of 1 node at level 1, and 2 nodes at level 2, which is obviously wrong if the root node is a level 0.

[JamesCherrill]

OK
I Googled and found that statement in Adam Drozdek's "Dara Structures and Algorithms in Java" (ditto in C++). BUT BUT BUT earlier in the same para he says "the root is at level 1".

[Amr.Mohammad87]

I've read it in many books "Data Structures and Algorithms in C++, 4th Edition by Adam Drozdek" also in "Data Structures Through C In Depth by S.k. Srivastava & Deepali Srivastava". I saw the paragraph you are talking about, however, in previous papers when he was listing the tree's terminology and he mentioned the level terminology he said that tree's level starts at 0.

[JamesCherrill]

Previous papers are irrelevant. It doesn't matter how many other papers number the root as level 0. In the paper where that statement is made the root is defined as level 1. That's the explanation.

[deceptikon]

Congratulations! You've found an inconsistency in terms with binary trees. :) There are actually a few of them, but counting levels is a notable one. As James said, each paper or book should be internally consistent, but you'll want to take care to follow the source material carefully. If you use multiple conflicting sources, pick one and convert the calculations of the others as necessary so that your stuff is internally consistent.

[Ben McNamara]

In modern Trees (AVL and Red/Black) there is actually a node above the root node called a header node. The parent of the root is the header and the parent of the header is the root. The header node is used for iteration of the tree - it does not contain data. Perhaps you could define the header node as level 0 and the root node as level 1.