Lower Bound Avg. II

• Because all non-leaves have two children, compressing the tree to make it more balanced will reduce the total sum of all path lengths.

C

X

A

B

Switch X and C

C

X

A

B

Path from root to C increases by 1,

Path from root to A&B decreases by 1,

Net reduction of 1 in the total.

Previous slide

Next slide

Back to first slide

View graphic version