Problem 5. Perfect Binary Tree Partition∗∗ .

A perfect binary tree is a rooted binary tree in which every non-leaf node has exactly two children and all the leaves are at the same depth. Note that a binary tree of height h will have exactly 2h leaves. Given a perfect binary tree with height h, let Sh = {2,3,...,2 h+1 −1} denote the set of all 2h+1 −2 nodes of the tree excluding the root. Let S1,...,Sh be a partition of Sh, that is, Si ∩ Sj = ∅ for all i 6= j, and ∪1≤i≤hSi = Sh. A partition is called unrelated if each set Si in the partition doesn’t contain two nodes in which one is an ancestor of the other (if u 6= v and u lies on the (unique) path from the root to v then u is called an ancestor of v while v is called a descendant of u). We define the balance index of a partition (S1,...,Sh) as the difference between the maximum size and the minimum size of a set in the partition. More formally,

a) Design an efficient algorithm (algorithm description, pseudo code, and an estimated time complexity if possible) that finds an unrelated partition of Sh that has minimum balance index. The algorithm is deemed efficient if the submitted implementation (Java/Python) can find an unrelated partition with balance index 0 or 1 for each h ≤ 10 in less than five seconds. Hint: iterative improvement.

b) Applicable if the algorithm can find an unrelated partitions with balance index 1 for h = 14 in less than 10 hours.

c) Provide a mathematical proof that the algorithm developed in Part a) can find an unrelated partition with balance index 0 or 1 for ALL h ≥ 2.

See the examples in Figure 3 for unrelated partitions of balance index 0/1 when h = 2,3. There can be other partitions satisfying the requirement. More details on how to prepare the solution for Problem 5 will be updated on Assignment 2 Queries (Discussion Forum).

Figure 3: Unrelated partitions with balance index 0 for h = 2 and balance index 1 for h = 3. Each set Si in a partition consists of nodes with the same color.