Provided class Odd: public class Odd { public boolean isOdd(Node r) { /* Input: Root r of a tree Output: true if all internal nodes of the tree have odd degree; false otherwise You can use the following methods from class Node: - numChildren() returns the number of children of a node. - isLeaf(): returns true if a node is a leaf and returns false otherwise To translate the following pseudocode for each child u of r do { ... } use the following java code: Node[] children = r.getChildren(); for (Node u : children) { ... } */ } }

i) (7 marks) Complete the provided Java class Odd.java by designing and implement in Java an algorithm isodd(r) that receives as input the root r of a tree and it outputs the value true if every internal node of the tree has odd degree, and it returns false otherwise. To test whether a number k is odd, you can use this statement: if ((k % 2) == 1) then k is odd. For example, for the tree below with root r the algorithm must output the value false, as node A has degree 4 (also the third child of node A has 2 children). For the tree with root r' the algorithm must return the value true. (ii) Compute the worst case time complexity of your algorithm as a function of the total number n of nodes in the tree. You must (1 mark) explain what the worst case for the algorithm is (2 marks) explain how you computed the time complexity (0.5 marks) give the order of the time complexity of the algorithm