3. [11 marks A leaf-to-root node path is a sequence of connected nodes V1, v2,... , vk where vi is a leaf and vk is the root of a tree. Consider the problem we will call the maximum-sum leaf-to-root problem: Given as input the root r of a tree (not necessarily binary) in which every node stores an integer value, return the value of the maximum leaf-to-root node path, where the value of a leaf-to-root node path is the sum of values of nodes in the path For example, the path J-E-B-A has value 1 +2+2+1 = 6, but the maxinuin-suin leaf-to-root path is M-F-B-A with value 4+4+2+1 11. Your algorithm is not responsible for finding the optimal path, just its value. Your algorithm must not modify the tree Node v.value 3 Design an algorithm that solves the max-sum leaf-to-root problem. For a node v use v.value to denote the value stored in v; 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: for each child c of v do You must... a) 7 marks Write pseudocode for the algorithm b) 4 markl 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 order of the time complexity of the algorithm 3. [11 marks A leaf-to-root node path is a sequence of connected nodes V1, v2,... , vk where vi is a leaf and vk is the root of a tree. Consider the problem we will call the maximum-sum leaf-to-root problem: Given as input the root r of a tree (not necessarily binary) in which every node stores an integer value, return the value of the maximum leaf-to-root node path, where the value of a leaf-to-root node path is the sum of values of nodes in the path For example, the path J-E-B-A has value 1 +2+2+1 = 6, but the maxinuin-suin leaf-to-root path is M-F-B-A with value 4+4+2+1 11. Your algorithm is not responsible for finding the optimal path, just its value. Your algorithm must not modify the tree Node v.value 3 Design an algorithm that solves the max-sum leaf-to-root problem. For a node v use v.value to denote the value stored in v; 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: for each child c of v do You must... a) 7 marks Write pseudocode for the algorithm b) 4 markl 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 order of the time complexity of the algorithm