CODEWITHSUNDEEP
data-structurestreebinary-tree
praxmon
praxmon

Reputation: 5121

What is the difference between a full binary tree and a complete binary tree?

A complete binary tree by my understanding can have incomplete nodes in the last level of the tree. What is a full binary tree? What is the difference?

Upvotes: 4

Views: 26068

Answers (3)

Tamil.S
Tamil.S

Reputation: 483

Perfect Binary Tree: 1. All the Internal nodes must having two children. 2. All the leaf nodes are at the same level.

Example :

         A1
     B1       B2
  C1    C2  C3  C4

Complete Binary Tree: All the levels are completely filled except possibly the last level

Example :

         A1
     B1       B2
  C1    C2  C3  C4
D1  D2 D3

Full Binary Tree: Simply Every node has 0 or 2 children.

Example :

         A1
     B1       B2
  C1    C2  C3  C4
D1  D2

Do update if the answer is aggree

Upvotes: 1

as g
as g

Reputation: 53

A complete binary tree is the most balanced tree for any no. of nodes. A full binary tree is what the most balanced tree would be if you have exactly (2^n) -1 nodes. Also, by convention, the empty space in a complete binary tree is kept at the right of the tree. edit: by most balanced, i mean the one with least depth for given no. of nodes.

Upvotes: 0

Raevik
Raevik

Reputation: 1991

A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.

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.

Here's the source for these descriptions and a picture for reference: http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

Upvotes: 4

Related Questions