A complete binary tree is a binary tree in which all level are completely filled: each non-leaf node has exactly 2 children and all leaves are located in the same level. Thus a tree of depth $n$ has 2$n$-1 nodes (1+2+4+8+$\cdots$). In this exercise, we represent a complete binary tree statically by an array that corresponds to the tree in width traversal (the root is at the index 0). In this exercise, we suppose that all tree values are distinct. Ex: the below array corresponds to the following BT:

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 6 & 4 & 0 & -2 & 5 & 3 & 10 & 7 & -4 & 18 & -1 & 9 & 11 & 13 & -7 \\ \hline \end{array}$

We define the ancestors of a leaf L as all nodes that are on the path from L to the root (including L). Thus, in this example, the ancestors of 18 are 18, 5, 4 and 6.

• \Write a function that takes a leaf L in parameter and computes the sum of L ancestors.
• Write a function that takes in parameters 2 leaves and computes the sum of their ancestors without repetition.
  Ex: for the leaves 7 and 18, the sum of ancestors is: 7-2+4+6+18+5 (4 and 6 are taken into account only once).

int sum_ancestor(int T[], int leaf)
{
    int sum=0;
    do
    {
        sum+=T[leaf];
        leaf=leaf/2;
        
    }while(leaf>0);
    return sum + T[leaf];
}

int sum_ancestors(int T[], int leaf1, int leaf2)
{
    int l1, l2;
    int sum=0;
    l1=MAX(leaf1,leaf2);
    l2=MIN(leaf1,leaf2);
    
    while(l1>0)
    {
        while(l1>l2 && l1>0)
        {
            sum+=T[l1];
            l1=l1/2;
        }
        while(l2>l1 && l2>0)
        {
            sum+=T[l2];
            l2=l2/2;
        }
        while(l2==l1 && l1>0)
        {
            sum+=T[l2];
            l1=l1/2;
            l2=l2/2;
        }
    }
    return sum + T[0];
}