36

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?

Improve this question

4 Answers 4

Reset to default
38

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Careful, there is no standard definition of "balanced binary tree" and there are variations: cs.stackexchange.com/questions/3515/… and the shown example at en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees
35

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

Improve this answer

Comments

1

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.

Improve this answer

1 Comment

It's the description of a perfect binary tree instead of complete. 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.
0

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

Improve this answer

2 Comments

It sounds like a tree is completely balanced if and only if it is full.
completely balanced trees are not necessarily full. The rule is: balanced trees are complete & full, complete or full, or neither. Unbalanced trees are never complete; they are full or neither.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.