Complete binary tree with n = 2^k-1 nodes. describe an algorithm to do this with O(lg n) worst case time complexity -

could please me solve question?

suppose there computer network topology complete binary tree n = 2^k-1 nodes k 1. assume transmission of data packet 1 node 1 of children (if any) in tree takes constant amount of time, i.e., o(1) time. also, assume there no packet loss. given that, need transmit 1 data packet root every node in network worst case time complexity of o(lg n). 2 nodes in tree can transmit packet simultaneously if use different edges. after receiving packet parent, left , right childern have separate copies of packet. also, there separate communication link between arbitrary pair of parent , child said before. how can write algorithm algorithm o(lg n) worst case time complexity how can prove worst time complexity of algorithm o(lg n) ?

i have tried 1 algorithm found online gives complexity o(n). not able send guys image have created solve problem because of low reputation.

assumptions: transmission of data packet 1 node 1 of children (if any) in tree takes constant amount of time, i.e., o(1) time. in above figure, root node transmitting data packet children takes constant amount of time o (1). same parent child combination in topology. there no packet loss. given that, need transmit 1 data packet root every node in network worst case time complexity of o (lg n). in above figure, nodes starting root every node other node in network acquired data packet transmitted root node. there no packet loss in topology

/* given binary tree, return true if tree complete    else false */ bool iscompletebt(struct node* root) {   // base case: empty tree complete binary tree   if (root == null)     return true;    // create empty queue   int rear, front;   struct node **queue = createqueue(&front, &rear);    // create flag variable set true   // when non full node seen   bool flag = false;    // level order traversal using queue.   enqueue(queue, &rear, root);   while(!isqueueempty(&front, &rear))   {     struct node *temp_node = dequeue(queue, &front);      /* ceck if left child present*/     if(temp_node->left)     {        // if have seen non full node, , see node non-empty left child,                                                        // given tree not complete binary tree        if (flag == true)          return false;         enqueue(queue, &rear, temp_node->left);  // enqueue left child     }     else // if non-full node, set flag true        flag = true;      /* ceck if right child present*/     if(temp_node->right)     {        // if have seen non full node, , see node non-empty left child,           // given tree not complete binary tree        if(flag == true)          return false;         enqueue(queue, &rear, temp_node->right);  // enqueue right child     }     else // if non-full node, set flag true        flag = true;   }    // if reach here, tree complete bianry tree   return true; } 

we use above algorithm check whether fulfills requirement of complete binary tree or not. if algorithm return true our topology complete binary tree , assumption transmitting data true.

time complexity: o (n) n number of nodes in given binary tree

the key answering understand question computer network, , not single computer. root node not need track delivery of nodes in network; needs delegate enough work child nodes ensure delivery reaches nodes in network.

in case, root node should transmit packet direct child nodes. each nonroot node, when receives packet direct parent node, should retransmit packet direct child nodes. allows nodes @ each level work in parallel, resulting in desired log(n) scaling of total delivery time.