Member Avatar for 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?!!!

  • 4 Contributors
  • 8 Replies
  • 202 Views
  • 1 Week Discussion Span
  • Latest Post Latest Post by Ben McNamara
Member Avatar for 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
Edited by JamesCherrill
Member Avatar for 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.

Member Avatar for 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.

Member Avatar for 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".

Member Avatar for 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.

Edited by Amr.Mohammad87
Member Avatar for 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.

Member Avatar for 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.

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.