top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Can a complete binary tree be full binary tree, please explain with an example?

+2 votes
870 views
Can a complete binary tree be full binary tree, please explain with an example?
posted Mar 28, 2016 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

0 votes

Lets first see what are these two animals -

Complete Binary Tree
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Full Binary Tree
A full binary tree is a binary tree in which every node other than the leaves has two children.

Now coming to your query, can complete binary tree be a full binary tree, answer is yes. See the following Complete Binary tree which is full also

        x
      /   \
     /     \
    x       x
   / \     / \
  x   x   x   x
 / \ 
x   x 

As except the leaf node all node has exactly two children.

answer Mar 28, 2016 by Salil Agrawal
0 votes

Full Binary Tree

Full binary tree (also called 2-tree or proper binary tree) is a tree in which every node has except the leaves, has two childrens

Complete Binary Tree

A complete Binary tree is a tree in which every node except possibly the last, is completely filled and all nodes are as far left as possible.
enter image description here

Conclusion

A Full binary tree can be Complete if nodes at last level are on the left side and completely filled (this case when there is no node on the right side at last level) and every node except leaves has 2 nodes.
For example: this one is full and also complete binary tree
enter image description here

A complete Binary tree can be full if and only if it follows all the rules of complete binary tree and has two children for each node other than leaves.
For example: This figure given below is Complete (because at every level nodes are completely filled except at last level,but all nodes at last level are on the left ) but not Full because one node at last level has only on children
enter image description here
But the figure below is Full and Complete Both.
enter image description here

answer Mar 28, 2016 by Shahsikant Dwivedi
...