BalancedTrees
TCO '03 Finals · 2003-10-07 · by vorthys
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.
Constraints
- k is between 1 and 100, inclusive.
- n is between 1 and 1000000, inclusive.
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
Submissions are judged against all 34 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BalancedTrees with a public method int maxHeight(int k, int n) · 34 test cases · 2 s / 256 MB per case