Complete binary tree and Perfect binary tree definitions

Question

I have few question about binary tree types.

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.

Almost every example for complete binary tree is given like that.One of the last nodes have only left child.

          18
       /       \  
     15         30  
    /  \        /  
  40    50    100

It's okay.

My question: Is the following tree also a complete binary tree?

           18
       /       \  
     15         30  
    /  \        
  40    50

I know it's full binary tree also.

My second question: If it is both full binary and complete binary tree can we say that it is also perfect binary tree? ( The last tree I wrote)

Jainik Jainik · Accepted Answer · 2019-02-08T07:34:18

1st Answer

Yes This tree can also be called as complete binary tree.

Explanation

Complete Binary Tree:

As you mentioned any tree in which all levels are completely filled and last level has keys as left as possible its considered binary tree. This condition satisfies for your example so its a complete binary tree.

Full Binary Tree:

Any binary tree in which all the nodes except leaf node has two children then its considered as full binary tree. 1st tree in question is not full binary tree but 2nd tree is full binary tree.

2nd Answer

No if tree is both full and complete that does not mean you can call it as a perfect binary tree.

A binary tree is considered perfect if it is full and all leaves are on the same level. In your example its not perfect binary tree.

Complete binary tree and Perfect binary tree definitions

1 Answers