2. 6 marks] Max-Tree Value. Consider the problem we will call the mar-tree value problem (MTV):...

Transcribed Image Text:

2. 6 marks] Max-Tree Value. Consider the problem we will call the mar-tree value problem (MTV): Given as input the root r of a tree (that is not necessarily binary) in which every node in the tree stores an integer value, return the value stored in a node of maximum value. For example, given the below tree, the algorithm should return value 44. Your algorithm is not responsible for returning the node, just its value. Your algorithm must not modify the tree. Node valse A T 15 " 12 D 36 E 1 F 2 G 6 1 9 M J 10 K 44 L M 10 Design a recursive algorithm that solves the MTV problem. For a node u use e.value to denote the value stored in ; v.isLeaf has value true if node v is a leaf and it has value false otherwise. To access the children of a node v use the following pseudocode: 3 for each childe of v do... You must... a) [3 marks] Write pseudocode (ie. not C++ code) for a recursive algorithm that solves the MTV problem. Please include 1-3 sentences before your pseudocode, in your own words, briefly describing what your algorithm does. To receive full marks, your pseu docode must be clear and has to be correct. b) [3 marks] Compute the worst-case time complexity of your algorithm as a function of the total number n of nodes in the tree. You must explain how you computed the time complexity, and give the time complexity of the algorithm using Big-Theta notation. 2. 6 marks] Max-Tree Value. Consider the problem we will call the mar-tree value problem (MTV): Given as input the root r of a tree (that is not necessarily binary) in which every node in the tree stores an integer value, return the value stored in a node of maximum value. For example, given the below tree, the algorithm should return value 44. Your algorithm is not responsible for returning the node, just its value. Your algorithm must not modify the tree. Node valse A T 15 " 12 D 36 E 1 F 2 G 6 1 9 M J 10 K 44 L M 10 Design a recursive algorithm that solves the MTV problem. For a node u use e.value to denote the value stored in ; v.isLeaf has value true if node v is a leaf and it has value false otherwise. To access the children of a node v use the following pseudocode: 3 for each childe of v do... You must... a) [3 marks] Write pseudocode (ie. not C++ code) for a recursive algorithm that solves the MTV problem. Please include 1-3 sentences before your pseudocode, in your own words, briefly describing what your algorithm does. To receive full marks, your pseu docode must be clear and has to be correct. b) [3 marks] Compute the worst-case time complexity of your algorithm as a function of the total number n of nodes in the tree. You must explain how you computed the time complexity, and give the time complexity of the algorithm using Big-Theta notation.