Consider a complete binary tree, i.e., nodes have either 0 or 2 children which can be...

  

Transcribed Image Text:

Consider a complete binary tree, i.e., nodes have either 0 or 2 children which can be accessed via pointers node.left and node.right and each node is also associated with a numeric key node.k. Note that the children pointers for leaves will be NULL. Employ a Divide and Conquer approach to sum the keys of all nodes in the tree: given a pointer to the root of the tree, divide into subtrees, sum values for them recursively, combine the results. a [10 pts.] State the actions to be taken during divide, conquer and combine. b [15 pts.] Provide the pseudo-code of the recursive sum() procedure that sums the keys for all nodes in the tree. c [10 pts.] What is the asymptotic running time O() of the algorithm for a tree of n nodes? Discuss your derivation. Consider a complete binary tree, i.e., nodes have either 0 or 2 children which can be accessed via pointers node.left and node.right and each node is also associated with a numeric key node.k. Note that the children pointers for leaves will be NULL. Employ a Divide and Conquer approach to sum the keys of all nodes in the tree: given a pointer to the root of the tree, divide into subtrees, sum values for them recursively, combine the results. a [10 pts.] State the actions to be taken during divide, conquer and combine. b [15 pts.] Provide the pseudo-code of the recursive sum() procedure that sums the keys for all nodes in the tree. c [10 pts.] What is the asymptotic running time O() of the algorithm for a tree of n nodes? Discuss your derivation.

Answer rating: 100% (QA)

The image contains a question about creating an algorithm to sum all the keys in a complete binary t... View the full answer