patternMinor
Is a balanced binary tree a complete binary tree?
Viewed 0 times
balancedbinarytreecomplete
Problem
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:
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.
Solution
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.
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.
The figure above describes this trees very clearly in a recursive way.
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.
The figure above describes this trees very clearly in a recursive way.
Context
StackExchange Computer Science Q#54171, answer score: 5
Revisions (0)
No revisions yet.