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$ Commented Nov 16, 2015 at 16:37
  • $\begingroup$ See here and here. $\endgroup$ Commented 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$ Commented Nov 16, 2015 at 16:43

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.