[Solved]: Example of height-balanced tree that is not weight-balanced

Problem Detail: 

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.

Asked By : OlivierLi

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49563

3.2K people like this

 Download Related Notes/Documents