BalancedTrees | Topcoder Archive

Problem Statement

Define the height of a binary tree to be the number of nodes in the longest path from the root to a leaf. The empty tree is considered to have height 0. A node is k-balanced if its left and right subtrees differ in height by at most k. A tree is k-balanced if all of its nodes are k-balanced. The empty tree is considered to be k-balanced.

For example, the tree below has height 4.

This tree is 2-balanced but not 1-balanced, because the left subtree of the root has height 3 and the right subtree of the root has height 1.

Your task is to write a method that takes a balance factor k and a number of nodes n and returns the maximum height of a k-balanced tree with n nodes.

Definition

Class:: BalancedTrees
Method:: maxHeight
Parameters:: int, int
Returns:: int
Method signature:: int maxHeight(int k, int n)
(be sure your method is public)

Constraints

k is between 1 and 100, inclusive.
n is between 1 and 1000000, inclusive.

Examples

```
1
```
```
7
```
```
Returns: 4
```
A tree that achieves the maximum height for 7 nodes and balance factor 1 is o / \ o o / \ \ o o o / o
```
2
```
```
40
```
```
Returns: 9
```
```
10
```
```
5
```
```
Returns: 5
```
With k=10, a tree of size 5 can be completely linear (eg, every right subtree is empty) without violating the balance factor.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.