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.
|