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.
o
/ \
o o
/ \
o o
/
o
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
2
39
Returns: 8
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.
100
1000000
Returns: 355
1
1000000
Returns: 28
3
788672
Returns: 40
3
788673
Returns: 41
77
777777
Returns: 287
78
777777
Returns: 289
64
524288
Returns: 243
100
100
Returns: 100
100
101
Returns: 101
100
99
Returns: 99
53
123456
Returns: 188
99
9801
Returns: 222
13
987654
Returns: 90
4
712937
Returns: 46
1
514228
Returns: 27
1
514227
Returns: 26
50
760
Returns: 87
13
65536
Returns: 71
27
900
Returns: 64
56
913928
Returns: 231
10
592831
Returns: 74
16
65536
Returns: 80
64
1024
Returns: 107
33
109238
Returns: 134
45
156
Returns: 59
19
192713
Returns: 99
7
107
Returns: 19
100
108271
Returns: 282
67
1995
Returns: 128
1
1
Returns: 1