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.
asked Mar 8, 2016 at 22:09
$\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$ Commented Mar 8, 2016 at 22:33

1 Answer 1

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.

answered Mar 9, 2016 at 16:50
$\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$ Commented May 24, 2022 at 6:56

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

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.