[data-structures] Difference between "Complete binary tree", "strict binary tree","full binary Tree"?

I am confused about the terminology of the below trees, I have been studying the Tree, and I am unable to distinguish between these trees:

a) Complete Binary Tree

b) Strict Binary Tree

c) Full Binary Tree

Please help me to differentiate among these trees. When and where these trees are used in Data Structure?

This question is related to data-structures tree binary-tree

The answer is


Consider a binary tree whose nodes are drawn in a tree fashion. Now start numbering the nodes from top to bottom and left to right. A complete tree has these properties:

If n has children then all nodes numbered less than n have two children.

If n has one child it must be the left child and all nodes less than n have two children. In addition no node numbered greater than n has children.

If n has no children then no node numbered greater than n has children.

A complete binary tree can be used to represent a heap. It can be easily represented in contiguous memory with no gaps (i.e. all array elements are used save for any space that may exist at the end).


Disclaimer- The main source of some definitions are wikipedia, any suggestion to improve my answer is welcome.

Although this post has an accepted answer and is a good one I was still in confusion and would like to add some more clarification regarding the difference between these terms.

(1)FULL BINARY TREE- A full binary tree is a binary tree in which every node other than the leaves has two children.This is also called strictly binary tree.

enter image description here enter image description here

The above two are the examples of full or strictly binary tree.

(2)COMPLETE BINARY TREE- Now, the definition of complete binary tree is quite ambiguous, it states :- 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. It can have between 1 and 2h nodes, as far left as possible, at the last level h

Notice the lines in italic.

The ambiguity lies in the lines in italics , "except possibly the last" which means that the last level may also be completely filled , i.e this exception need not always be satisfied. If the exception doesn't hold then it is exactly like the second image I posted, which can also be called as perfect binary tree. So, a perfect binary tree is also full and complete but not vice-versa which will be clear by one more definition I need to state:

ALMOST COMPLETE BINARY TREE- When the exception in the definition of complete binary tree holds then it is called almost complete binary tree or nearly complete binary tree . It is just a type of complete binary tree itself , but a separate definition is necessary to make it more unambiguous.

So an almost complete binary tree will look like this, you can see in the image the nodes are as far left as possible so it is more like a subset of complete binary tree , to say more rigorously every almost complete binary tree is a complete binary tree but not vice versa . :

enter image description here


Concluding from above answers, Here is the exact difference between full/strictly, complete and perfect binary trees

  1. Full/Strictly binary tree :- Every node except the leaf nodes have two children

  2. Complete binary tree :- Every level except the last level is completely filled and all the nodes are left justified.

  3. Perfect binary tree :- Every node except the leaf nodes have two children and every level (last level too) is completely filled.


To start with basics, it is very important to understand binary tree itself to understand different types of it.

A tree is a binary tree if and only if :-

– It has a root node , which may not have any child nodes (0 childnodes, NULL tree)

–Root node may have 1 or 2 child nodes . Each such node forms abinary tree itself 

–Number of child nodes can be 0 ,1 ,2.......not more than 2

–There is a unique path from the root to every other node

Example :

        X
      /    \
     X      X
          /   \
         X     X

Coming to your inquired terminologies:

A binary tree is a complete binary tree ( of height h , we take root node as 0 ) if and only if :-

Level 0 to h-1 represent a full binary tree of height h-1

– One or more nodes in level h-1 may have 0, or 1 child nodes

If j,k are nodes in level h-1, then j has more child nodes than k if and only if j is to the left of k , i.e. the last level (h) can be missing leaf nodes, however the ones present must be shifted to the left

Example :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 

A binary tree is a strictly binary tree if and only if :-

Each node has exactly two child nodes or no nodes

Example :

         X
       /   \
      X     X 
          /   \
         X      X
        / \    / \ 
       X   X  X   X 

A binary tree is a full binary tree if and only if :-

Each non leaf node has exactly two child nodes

All leaf nodes are at the same level

Example :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 
      /  \  / \ / \ / \      / \  / \  / \ / \ 
     X   X X  X X X X X     X  X  X X  X X X X 

You should also know what a perfect binary tree is?

A binary tree is a perfect binary tree if and only if :-

– is a full binary tree

– All leaf nodes are at the same level

Example :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 
      /  \  / \ / \ / \      / \  / \  / \ / \ 
     X   X X  X X X X X     X  X  X X  X X X X 

Well, I am sorry I cannot post images as I do not have 10 reputation. Hope this helps you and others!


Full binary tree are a complete binary tree but reverse is not possible, and if the depth of the binary is n the no. of nodes in the full binary tree is ( 2^n-1 ). It is not necessary in the binary tree that it have two child but in the full binary it every node have no or two child.


In my limited experience with binary tree, I think:

  1. Strictly Binary Tree:Every node except the leaf nodes have two children or only have a root node.
  2. Full Binary Tree: A binary tree of H strictly(or exactly) containing 2^(H+1) -1 nodes , it's clear that which every level has the most nodes. Or in short a strict binary tree where all leaf nodes are at same level.
  3. Complete Binary Tree: It is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Complete Binary Tree: All levels are completely filled except the lowest level and one main thing all the leaf elements must have left child. Strict Binary Tree: In this tree every non-leaf node has no child i.e. neither left nor right. Full Binary Tree: Every Node has either zero child or Two children (never having single child).


Let us consider a binary tree of height 'h'. A binary tree is called a complete binary tree if all the leaves are present at height 'h' or 'h-1' without any missing numbers in the sequence.

                   1
                 /   \
              2       3
            /    \         
         4        5

It is a complete binary tree.

                   1
                 /   \
              2       3
            /        /    
         4         6    

It is not a complete binary tree as the node of number 5 is missing in the sequence


There is a difference between a STRICT and FULL BINARY TREE.

1) FULL BINARY TREE: A binary tree of height h that contains exactly (2^h)-1 elements is called a full binary tree. (Ref: Pg 427, Data Structures, Algorithms and Applications in C++ [University Press], Second Edition by Sartaj Sahni).

or in other words

In a FULL BINARY TREE each node has exactly 0 or 2 children and all leaf nodes are on the same level.

For Example: The following is a FULL BINARY TREE:

          18
       /      \   
     15       30    
    /  \     /   \   
  40    50  100  40 

2) STRICT BINARY TREE: Each node has exactly 0 or 2 children.

For example: The following is a STRICT BINARY TREE:

         18
       /     \   
     15       30    
    /  \          
  40    50

I think there's no confusion in the definition of a Complete Binary Tree, still for the completeness of the post I would like to tell what a Complete Binary Tree is.

3) 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.

For Example: The following is a COMPLETE BINARY TREE:

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40
 /  \   /
8   7  9 

Note: The following is also a Complete Binary Tree:

         18
       /     \   
     15       30    
    /  \     /   \   
  40    50  100  40 

full binary tree is full if every node has 0 or 2 children. in full binary number of leaf nodes is number of internal nodes plus 1 L=l+1


Perfect Tree:

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

Complete Tree:

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

Strict/Full Tree:

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

Examples related to data-structures

Program to find largest and second largest number in array golang why don't we have a set datastructure How to initialize a vector with fixed length in R C compiling - "undefined reference to"? List of all unique characters in a string? Binary Search Tree - Java Implementation How to clone object in C++ ? Or Is there another solution? How to check queue length in Python Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Write code to convert given number into words (eg 1234 as input should output one thousand two hundred and thirty four)

Examples related to tree

Tree implementation in Java (root, parents and children) Build tree array from flat array in javascript Binary Search Tree - Java Implementation Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Tree view of a directory/folder in Windows? Definition of a Balanced Tree Difference between binary tree and binary search tree How to create a collapsing tree table in html/css/js? How to search JSON tree with jQuery Non-recursive depth first search algorithm

Examples related to binary-tree

Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Difference between binary tree and binary search tree Heap vs Binary Search Tree (BST) C linked list inserting node at the end How to print binary tree diagram? With ' N ' no of nodes, how many different Binary and Binary Search Trees possible? How to implement a binary tree? Find kth smallest element in a binary search tree in Optimum way What are the applications of binary trees? How to find the lowest common ancestor of two nodes in any binary tree?