Difference between Complete binary tree and balanced binary tree

A balanced binary tree is the binary tree where the depth of the two subtrees of every node never differ by more than 1.

A complete binary tree is a binary tree whose all levels except the last level are completely filled and all the leaves in the last level are all to the left side.

Below is a balanced binary tree but not a complete binary tree. Every complete binary tree is balanced but not the other way around.

        1
     1     1
   1   1     1
 1 

As implies, in a complete tree, always the level difference will be no more than 1 so it is always balanced.

Since this developed into further questions about perfect, balanced, complete, and full - here is an answer that clarifies those as well. Assuming a a binary tree,

1. Balanced: The left and right subtrees of every node differ in height by no more than 1.

2. Full: All nodes except leaf nodes have 2 children

3. Complete:

   • All nodes except for the level before the last must have 2 children.
   • All nodes in the last level are as far left as possible.

Summary:

• Complete trees: must be balanced; can be full
• Full trees: can be balanced; can be complete
• Balanced trees: can be complete; can be full

Examples:

---

• Full & balanced - All nodes have 0 or 2 children, level 3 - level 2 <= 1, (Not complete - last level nodes are not as far left as possible)

         1             --- LEVEL 0
       /    \
      1      1         --- LEVEL 1
     /\      /\
    1  1    1  1       --- LEVEL 2
    -  /\   -  -
      1  1             --- LEVEL 3
  x x -  - 
  

• Full, balanced & complete - All nodes have 0 or 2 children, 3 - 2 <= 1, last level nodes are as far left as possible:

         1             --- LEVEL 0
       /    \
      1      1         --- LEVEL 1
     /\      /\
    1  1    1  1       --- LEVEL 2
   /\  -    -  -
  1  1                 --- LEVEL 3
  -  - 
  

• Full - All nodes have 0 or 2 children (Unbalanced - 3 - 1 > 1, Not complete - level 1 has a node with 0 children):

        1              --- LEVEL 0
       / \
      1   1            --- LEVEL 1
     / \  -
    1   1              --- LEVEL 2
   / \  - x x
  1   1                --- LEVEL 3
  -   -
  

• Complete & balanced - Last level nodes are as far left as possible, 3 - 3 <= 1 (Not full - there is a level 2 node with 1 child):

         1             --- LEVEL 0
       /    \
      1      1         --- LEVEL 1
     /\      /\
    1  1    1  1       --- LEVEL 2
   /\  /\  /\  /x
  1 1 1  11 1 1        --- LEVEL 3
  - - -  -- - -
  

• Balanced - 3 - 3 <= 1, (Not full - there is a level 2 node with 1 child, Not complete - last level nodes are not as far left as possible)

         1             --- LEVEL 0
       /   \
      1     1          --- LEVEL 1
     /\     /\
    1  1   1  1        --- LEVEL 2
   /\ /\  /x  /\
  1 11  11   1  1      --- LEVEL 3
  - --  -- x -  -
  

---

4. Perfect: All interior nodes have two children and all leaves have the same depth.

None of the above examples are perfect

Balanced Tree : A balanced tree is that form of binary tree in which the difference of left subtree's height and right subtree's height at every node will be atmost k, where k will be the balancing factor . If this balancing factor turn out to be 0 then that tree will be called fully balanced tree .

Example :
                          8
                    6         1
                3          9     1

This tree is balanced tree with balanced factor 1 as diff in height of each node's subtree is either 0 or 1.

Complete binary tree: A tree is said to be complete if apart from leaf's each level is completely filled . And any new insertion on the leaf node will be from left to right which means leaf at left level will be filled completely first.

Example :                    8
                             6            1
                         3     5      4     1

Now this tree is complete binary tree and if any new insertion has to be done then it should be under leaf at left which is 3 in this example . Once 3 is filled with left and right child then 5 will be the next leaf for new insertion.