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?
3 Answers
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:
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.
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
