My textbook says a "complete binary tree" is a "full binary tree" where every root is at the same level.

My conceptual understanding:

All this time, I was led by my textbook to believe a root is the "top-most vertex" in which all the other vertex are led away from it. So basically I am led to believe there can be only one root in a tree.


What does "where every root is at the same level" even mean?

Isn't a root suppose to be at level 0 all the time?

  • 3
    $\begingroup$ Are you sure it doesn't say every leaf is at the same level? $\endgroup$
    – Louis
    May 1, 2015 at 6:49
  • $\begingroup$ Nope. The textbook says "The graph representing such a network is a complete binary tree, that is, a full binary tree where every root is at the same level." page 751"Discrete Mathematics and its Application 7th edition written by Kenneth Rosen. I think your statement is referring to "balanced rooted trees" if my memory serves me right. $\endgroup$
    – Nicholas
    May 1, 2015 at 6:53
  • 4
    $\begingroup$ It is a typo then. A full binary tree means that every internal node has either 0 or 2 children. A complete one is then a full tree with all the leaves the same distance from the root. $\endgroup$
    – Louis
    May 1, 2015 at 7:09
  • $\begingroup$ Isn't a full binary tree the same thing as a "2-ary tree"? I thought the internal node must have exactly 2 children for full binary tree. My textbook never spoke about internal nodes having 0 children for full binary tree. $\endgroup$
    – Nicholas
    May 1, 2015 at 7:29
  • 2
    $\begingroup$ Another point in favor of a typo is "every root". How many roots is a full binary tree supposed to have? If the answer is 1, then the condition is trivially satisfied for any full binary tree. A member of a singleto set shares all its properties with all other members of the same set. :) $\endgroup$
    – babou
    May 1, 2015 at 10:14

1 Answer 1


It basically is a typo, every leaf at same level may be the correct words


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.