Search code examples
data-structuresbinary-tree

Difference between Complete binary tree and balanced binary tree


What is the difference between a balanced binary tree and a complete binary tree?
Is it true to say every complete binary tree is a balanced tree?
How about the other way around?


Solution

  • 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.