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$
2
  • 1
    $\begingroup$ You should try harder. $\endgroup$ Commented Nov 16, 2015 at 16:37
  • $\begingroup$ See here and here. $\endgroup$ Commented Nov 16, 2015 at 17:29

1 Answer 1

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.

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

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.