3
$\begingroup$

Considering that the opposite is true it's not mentioned anything about this. I am assuming its not, but I need a very good distinction between these two types of binary trees.

All I know is this:

  • A binary tree is balanced (or height balanced), if the height of any node’s right subtree and left subtree differ no more than $1$.
  • A complete binary tree of height h is a binary tree that is full down to level $h-1$, with level $h$ filled in from left to right.
Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ Take it as an exercise to find a balanced binary tree which isn't complete, and on the other hand to prove that every complete binary tree is balanced. Try to use the definitions. $\endgroup$
    – Yuval Filmus
    Mar 8, 2016 at 22:33

1 Answer 1

Reset to default
5
$\begingroup$

A complete binary tree is a binary tree of length $h$ such that all the levels from $1$ to $h-1$ are completed and the last level gets completed from left to right. As in the image below.
Complete Binary Tree

A balanced binary tree is a binary tree of height $h$ such that the height of any node’s right subtree and left subtree differ no more than $1$. So it doesn't say anything about it having to be completed from left to right. enter image description here

The figure above describes this trees very clearly in a recursive way.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Could we not define a balanced binary tree the same way as a complete binary tree, just without the restraint of the leaves of the last level being added left to right? eg: A balanced binary tree has all levels filled except possibly the last, instead of saying "the height of any node's right subtree and left subtree differ no more than 1". What's the difference? $\endgroup$
    – user4779
    May 24, 2022 at 6:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.