Minimum no. of iterations to pass information to all nodes in the tree - GeeksforGeeks

Minimum no. of iterations to pass information to all nodes in the tree - GeeksforGeeks

Given a very large n-ary tree. Where the root node has some information which it wants to pass to all of its children down to the leaves with the constraint that it can only pass the information to one of its children at a time (take it as one iteration).

Now in the next iteration the child node can transfer that information to only one of its children and at the same time instance the child’s parent i.e. root can pass the info to one of its remaining children. Continuing in this way we have to find the minimum no of iterations required to pass the information to all nodes in the tree.

Minimum no of iterations for tree below is 6. The root A first passes information to B. In next iteration, A passes information to E and B passes information to H and so on.

Let minItr(A) be the minimum iteration needed to pass info from node A to it’s all the sub-tree. Letchild(A) be the count of all children for node A. So recursive relation would be:

1. Get minItr(B) of all children (B) of a node (A)
2. Sort all minItr(B) in descending order
3. Get minItr of A based on all minItr(B)
    minItr(A) = child(A)
    For children B from i = 0 to child(A)
             minItr(A) = max ( minItr(A), minItr(B) + i + 1)

Base cases would be:
If node is leaf, minItr = 0
If node's height is 1, minItr = children count 

/* A recursive function to used by getMinIter(). This function

// mainly does postorder traversal and get minimum iteration of all children

// of node u, sort them in decreasing order and then get minimum iteration

// of node u

 

1. Get minItr(B) of all children (B) of a node (A)

2. Sort all minItr(B) in descending order

3. Get minItr of A based on all minItr(B)

    minItr(A) = child(A) -->> child(A) is children count of node A

    For children B from i = 0 to child(A)

             minItr(A) = max ( minItr(A), minItr(B) + i + 1)

 

Base cases would be:

If node is leaf, minItr = 0

If node's height is 1, minItr = children count

*/

 

void NAryTree::getMinIterUtil(int u, int minItr[])

{

    minItr[u] = adj[u].size();

    int *minItrTemp = new int[minItr[u]];

    int k = 0, tmp = 0;

    // Recur for all the vertices adjacent to this vertex

    list<int>::iterator i;

    for (i = adj[u].begin(); i!= adj[u].end(); ++i)

    {

        getMinIterUtil(*i, minItr);

        minItrTemp[k++] = minItr[*i];

    }

    qsort(minItrTemp, minItr[u], sizeof (int), compare);

    for (k = 0; k < adj[u].size(); k++)

    {

        tmp = minItrTemp[k] + k + 1;

        minItr[u] = max(minItr[u], tmp);

    }

    delete[] minItrTemp;

}

  

// The function to do PostOrder traversal. It uses

// recursive getMinIterUtil()

int NAryTree::getMinIter()

{

    // Set minimum iteration all the vertices as zero

    int *minItr = new int[N];

    int res = -1;

    for (int i = 0; i < N; i++)

        minItr[i] = 0;

  

    // Start Post Order Traversal from Root

    getMinIterUtil(0, minItr);

    res = minItr[0];

    delete[] minItr;

    return res;

}

Read full article from Minimum no. of iterations to pass information to all nodes in the tree - GeeksforGeeks