16
$\begingroup$

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

Improve this question
$\endgroup$
1

4 Answers 4

Reset to default
32
$\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
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ For me the term "complete binary tree" means what you call "perfect binary tree". $\endgroup$
    – Yuval Filmus
    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$
    – Yuval Filmus
    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.

Improve this answer
$\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$
    – Hendrik Jan
    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

Improve this answer
$\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.

Improve this answer
$\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$
    – David Richerby
    Nov 17, 2016 at 8:48

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.