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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You should try harder. $\endgroup$
    – Yuval Filmus
    Nov 16, 2015 at 16:37
  • $\begingroup$ See here and here. $\endgroup$
    – Raphael ♦
    Nov 16, 2015 at 17:29

1 Answer 1

Reset to default
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.

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

Your Answer

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

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