Given a binary tree - T, and a real number , T would be defined as ' K - Balanced ' ' iff the ratio between the shortest path from T's root to some external - leaf of T (measured in number of vertices) and the longest such path is at most k.

Furthermore, T is to be considered ' FULLY - K - BALANCED ' iff any sub-tree of T also satisfies the ' K - Balanced ' property.

Q. Based on the definitions above, find an algorithm such that for a given binary - tree T - determines the smallest constant for which T would be ' FULLY - K - BALANCED ' .

* The algorithm should be as efficient as possible (in term of ' Big - O - Notation ').

Transcribed image text