Difference between Complete binary tree and balanced binary tree

data-structures binary-tree
sheidaei picture sheidaei · Feb 7, 2013 · Viewed 17.6k times · Source

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?

Answer

sheidaei picture sheidaei · Feb 7, 2013

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.

Related questions

How to print binary tree diagram?

How can I print a binary tree in Java so that the output is like: 4 / \ 2 5 My node: public class Node<A extends Comparable> { Node<A> left, right; A data; public Node(A data){ this.data = data; } }

Read More
Difference between binary tree and binary search tree

Can anyone please explain the difference between binary tree and binary search tree with an example?

Read More
How to implement a binary tree?

Which is the best data structure that can be used to implement a binary tree in Python?

Read More