What is a good approximation for the maximum height of the tree? (Module 8 - Approach)

Apologies for the wrong tag, I couldn’t find the relevant tag.
For module 8 approach pack, the constraints mention that

  • The tree is balanced
  • The maximum number of nodes in the tree can be 50000

Based on these constraints, I assumed that a good approximation for the upper bound of the tree height would be about log2(100000) = 17, so I tried to check for each depth from 1 to 20 for good measure. However, it failed all performance tests. When I changed the upper limit to 30, surprisingly the assessment passed. Please help me understand when would the height of a balanced binary tree be more than log2(N)?

Hey good work solving the question. You are probably confused about the lower bound and higher bound. To tell you the difference :

  1. For a balanced binary tree, the minimum height will be ceil(log2(n+1)) which is the lower bound (when root is considered at a height of 1)
  2. For a balanced binary tree, the minimum height will be floor(1.44*log2(n+2)-.328) which is the upper bound (when root is considered at a height of 1) .

To understand, why this happends,you can click here and read a discussion on the minimum and maximum length for a balanced tree. Hopefully you found this helpful.

1 Like

Closing this topic as your issue is resolved by the mentor. If it is still not resolved, Kindly un-mark the accepted solution or create a new topic and post this question as a reference link in the description of the new topic.