Complete vs Perfect/Full binary tree
Data-structures #binary-tree #data-structuresPerfect or Full binary tree
Full binary tree is a type of
binary treewhere each parent node has either two or no children
Or
A full binary tree contains the maximum number of nodes for the height of that tree i.e. adding another node will increase the height of the tree
Keeping in mind that the height of a binary tree is equal to 2h+1-1, a complete binary with
height h=3 should contain 7 nodes. (see example B below)
In the following examples, tree A & Bare full binary trees but tree C & D are not (find out why?)
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 in the last level are as far left as possible - wikipedia
A complete binary tree needs to satisfy these two properties
- A complete binary tree is a
full binary treeup to the levelh-1 - On last level it can have between
1to2hnodes but nodes are filled fromleftto right.
In the following examples A & B are complete binary trees because they satisfy the above two properties.
C & D are not complete binary trees because C does not satisfy the 2nd property while D doesn’t satisfy any of the above-mentioned properties.
Height of a complete binary tree will always be minimum that is
log n