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.
-
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– Yuval Filmus2016年03月08日 22:33:40 +00:00Commented Mar 8, 2016 at 22:33
1 Answer 1
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.
-
$\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– user47792022年05月24日 06:56:23 +00:00Commented May 24, 2022 at 6:56