1
$\begingroup$

I am reading the book "Cracking the coding interview". In Chapter 4 they cover basic tree concepts.

It says there that a complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right. Thus, the following binary tree is complete:

         1
     2       3
   4   5   6

A full binary tree is a binary tree in which every node has either zero or two children. This is clear and self-explanatory.

Now, a perfect binary tree is the one that is both full and complete. It is said that in a perfect binary tree all leaf nodes will be at the same level, and this level has the maximum number of nodes.

However, the following binary is full and complete (according to the given definition), but it does not have all of the levels completely filled:

         1
     2       3
   4   5

Can someone experienced in this terminology clarify this point? It looks like a mistake in the definition.

Improve this question
$\endgroup$
3
  • $\begingroup$ a difference of terminology, but i would call that complete tree example as 'almost complete'. Then you can see, the perfect tree example of yours isn't actually a perfect tree, which is correct. $\endgroup$
    – Rinkesh P
    Jul 28, 2022 at 16:39
  • $\begingroup$ @Mikhail It is possible that book is either explaining the concept instead of defining the concept, or continuing the definition even after the full stop, ".". For another example, the book reads, "A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right." Note that a complete binary tree must fill the last level from left to right. However, that condition is not implied by "every level of the tree is fully filled, except for perhaps the last level." $\endgroup$
    – John L.
    Jul 28, 2022 at 16:56
  • 1
    $\begingroup$ By the way, the last example in the question is in the same shape of the distinguished logo/favicon of this website. $\endgroup$
    – John L.
    Jul 28, 2022 at 18:14

1 Answer 1

Reset to default
2
$\begingroup$

Here is the relevant text on that book, sixth edition.

Perfect Binary Trees

A perfect binary tree is one that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.

As you have observed, the statements quoted above is somewhat ambiguous and confusing if not downright wrong. While a perfect binary must be a full and complete binary tree, a full and complete binary tree is not necessarily a perfect binary tree.

The definition of a perfect binary tree can be any one of the following.

  • A perfect binary tree is a full and complete binary tree where all leaf nodes are at the same level, and this level has the maximum number of nodes.
  • A perfect binary tree is a complete binary tree where all leaf nodes are at the same level, and this level has the maximum number of nodes.
  • A perfect binary tree is a binary tree where every level is fully filled.
  • A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level. (This definition comes from Wikipedia).
  • A perfect binary tree is a binary tree of level $k$ and $2^k-1$ nodes for some positive integer $k$. (Or non-negative integer $k$ if a binary tree is allowed to have no nodes.)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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