12
$\begingroup$

Is there a difference between perfect, full and complete tree? Or are these the same words to describe the same situation?

$\endgroup$
1

4 Answers 4

27
$\begingroup$

Yes, there is a difference between the three terms and the difference can be explained as:

Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree.

         18
       /    \   
     15      20    
    /  \       
   40   50   
  /  \
 30  50

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.

            18
       /         \  
     15           30  
    /  \         /  \
  40    50     100   40
 /  \   /
8   7  9 

Perfect Binary Tree: A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40
$\endgroup$
4
  • 1
    $\begingroup$ For me the term "complete binary tree" means what you call "perfect binary tree". $\endgroup$ Jul 29, 2017 at 13:35
  • $\begingroup$ no, they aren't the same. As you can see in the above example, all the leaves in the complete binary tree are not at the same level whereas in case of perfect binary tree they must be at the same level. $\endgroup$
    – Lov Verma
    Jul 29, 2017 at 18:18
  • 2
    $\begingroup$ What I'm implying is that your terminology is not really standard. Other people mean something else when they use the exact same expressions. $\endgroup$ Jul 29, 2017 at 22:15
  • $\begingroup$ okay got that. I'll provide u with a better answer shortly. Thanks for your response. $\endgroup$
    – Lov Verma
    Jul 30, 2017 at 4:03
4
$\begingroup$

These words don't have a standard definition. A full binary tree could be one in which every node has either none or two children. A complete binary tree of height $h$ could be one in which all nodes up to level $h$ have two children. I have never heard of the adjective perfect used to describe trees.

That said, a complete binary tree of height $h$ usually means what I wrote above.

$\endgroup$
2
  • $\begingroup$ There's also one of these for trees that are complete up to height $h-1$, and level $h$ is filled "from the right". (Tree representations of heaps look this way.) $\endgroup$
    – Raphael
    Oct 28, 2014 at 7:33
  • $\begingroup$ Tree representations of heaps are complete, if additionally the last level is filled then it is perfect. $\endgroup$ Oct 28, 2014 at 12:39
1
$\begingroup$

A complete binary tree is on in which every level excepts possible the last level is completely filled and every node are as far left as possible but for a full binary tree every level has the maximum number of nodes in it

$\endgroup$
0
$\begingroup$

A full binary tree has all it's nodes with either none or two children. A complete binary tree of height h could be one in which all nodes up to level h have two children. A perfect binary tree is a tree which is both full and complete.

$\endgroup$
1
  • 1
    $\begingroup$ Says who? The accepted answer says that these terms have multiple inconsistent definitions so how can you say that one definition is the only correct one? $\endgroup$ Nov 17, 2016 at 8:48

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.