CODEWITHSUNDEEP
data-structuresbinary-tree
sheidaei
sheidaei

Reputation: 10332

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?

Upvotes: 35

Views: 33594

Answers (4)

user7247147
user7247147

Reputation: 1107

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 either 0 or 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 -  -
  1. Perfect: All interior nodes have two children and all leaves have the same depth.

None of the above examples are perfect

Upvotes: 34

Pooja
Pooja

Reputation: 31

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.

Upvotes: 1

hpl002
hpl002

Reputation: 609

Tree is said to be full when a a binary tree of height h has all of its leaves at level h and every parent has exactly two children

Tree is said to be complete when all levels but the last contain as many nodes as possible, and the nodes on the last level are filled in from left to tight. (Not full, but complete)

When each node in a binary tree has two subtrees who's heights are exactly the same the tree is said to be completely balanced

Completely balanced trees are full

A tree is height balanced or simply balanced if the subtrees of a node differ by no more than one

Upvotes: 0

sheidaei
sheidaei

Reputation: 10332

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.

Upvotes: 38

Related Questions