Problem 5. The n nodes of a rooted complete binary tree can be indexed by the set [0,n−1] , {0,1,...,n−1} in the natural order (top to bottom, left to right). A labelling or permutation p is a map that assigns to each vertex i ∈ [0,n−1] a label p[i] ∈ [0,n−1] so that different nodes have different labels. A labelling p is called magical if it satisfies the following condition: if we assign to each edge (i, j) of the tree the label |p[i] − p[j]|, i.e., the absolute value of the difference between the labels of Node i and Node j, then all edge labels must all be distinct. We can also treat p as a permutation of the vertice labels. See Fig. 5 for an example of such labellings/permutations on trees of n = 5 and n = 8 nodes. In these cases, the labellings are p = [0,4,2,1,3] and p = [3,0,5,7,6,4,1,2]. Note that for the first labelling, p[0] = 0, p[1] = 4, p[2] = 2, p[3] = 1, p[4] = 3.

Figure 5: Examples of magical labellings p = [0,4,2,1,3] and p = [3,0,5,7,6,4,1,2] for complete binary trees of n = 5 and n = 8 nodes, respectively. The edge labels (in red) are calculated by taking the absolute values of the differences between the labels of two incident nodes, e.g., for the 5-node tree, the edge connecting the root and its left child has label |p[0]− p[1]| = |0−4| = 4. Both labellings are magical because all edge labels are distinct.

a) Design an efficient algorithm (algorithm description, pseudo code, examples, Python code, and an estimated time complexity if possible) that finds a magical labelling p for every rooted complete binary tree of n nodes. The algorithm is deemed efficient if the submitted implementation in Python can find magical labellings for ALL 1 ≤ n ≤ 19 in less than 5 minutes on a laptop. All 19 output magical labellings/permutations must be included in file permutations.txt submitted along the code. A Python code to test these permutations is available on Assignment 2: General Discussion (Ed Discussion Forum).

b) Provide a mathematical proof that the algorithm developed in Part a) can find a magical labelling for complete binary of n nodes for ALL n ≥ 1.