0
$\begingroup$

Binary tree with external leaves is a 5-balanced tree if the path from the root to the farthest external leaf is no more than 5 times as long as the path from the root to the nearest external leaf, and if his right and left subtrees are 5-balanced too. Show that the height of such a tree is O(logn).

I was trying to prove it by finding the minimum number of nodes in such a tree with height h and then saying that the height of the tree is at most the log of this number, but I'm not sure how to find it. Thanks

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Not sure how to find what? Your approach sounds promising; where specifically did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W. ♦
    Commented Jul 25, 2017 at 15:26

1 Answer 1

Reset to default
2
$\begingroup$

Suppose that the tree has depth $D$. Then all leaves are at distance at least $D/5$ from the root, which means that the tree contains the full binary tree of depth $D/5$ as a subtree. This implies that $n \geq 2^{D/5}$, and so $D = O(\log n)$.

Note that this argument doesn't use the recursive part of the definition.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.