Problem 1-4. Sum your ancestors [30 points] You are given a complete binary tree

Question

Problem 1-4. Sum your ancestors [30 points] You are given a complete binary tree of height h with n 2 leaves, where each node (internal nodes and leaves) of the tree has an associated value v (which is an arbitrary real number If r is a leaf, we denote by A(), the set of ancestors of r (including r as one of its own ancestors). That is, A( contains z, r's parent, r's grandparent, etc. up to the root of the tree. Similarly, if x and y are distinct leaves, we denote A(z, y) as the ancestors of either x or y. That is A(x,y)- A(r) U A(y). We define a function f(r, y) as the sum of all values of the nodes in A(r, y). An example is shown in Figure 1 Give a parallel algorithm that efficiently finds two leaves ro and yo such that f(ro, yo) is as large as possible (largest among all the pairs of leaves). Analyze the work and span of your algorithm. 30 10 36 12 15 10 7 9 16 19 27 13 Figure 1: A(r, y) is shown in bold. f(, y)- 19 +15 36+10+27+30 the value of f(r, y) is maximized for the leaves r andy 137. For this tree,

Explanation / Answer

This can be done in O(n) .

int maxSum(struct Node *root, int &result)
{
//base case
if (root==NULL) return 0;
if (!root->left && !root->right) return root->data;

int leftSum = maxSum(root->left, result);
int rightSum = maxSum(root->right, result);

if (root->left && root->right)
{
  
result = max(result, leftSum + rightSum + root->data);   
return max(leftSum, rightSum) + root->data;
}
  
return (!root->left)? rightSum + root->data:leftSum + root->data;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.