2
$\begingroup$

Following this question : Two definitions of balanced binary trees

I am having a hard time making sense of the proofs provided and I'm looking for an example of a simple binary tree that is height-balanced but not weight-balanced.

This would mean that we could clearly see the height differences of two sub-trees being more than one while the maximum depth difference of any two leave nodes would never be more than one.

Does such an example exist?

EDIT: This question was asked because I misunderstood the inner-node concept. I was looking for a tree example where the height of two sub trees differed by more than one while the the maximum depth and minimum depth had a difference of no more than one.

$\endgroup$
  • 1
    $\begingroup$ You should try harder. $\endgroup$ – Yuval Filmus Nov 16 '15 at 16:37
  • $\begingroup$ See here and here. $\endgroup$ – Raphael Nov 16 '15 at 17:29
3
$\begingroup$

Take a complete binary tree of height 2 (with 7 vertices), and add two children to the two left leaves. The tree is height-balanced but the root is not weight-balanced.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I was confused about the definition of "inner-nodes". $\endgroup$ – OlivierLi Nov 16 '15 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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