O. (@) A collection of nodes is arranged as a binary search tree ordered on the he which contains distinct positive integers for each of the mode. In addition to INFO, LLINK and RLINK. each node has three other fields CLASS, SUCC and PRED CLASS is an information field containing a single letter that denotes the class to which the node belongs (there being up to 26 classes). The nodes in each class are arranged as a doubly linked circular list with a list head, by using the pointer fields SUCC and PRED to point to the successor and predecessor of a node in the list, respectively. The format of the nodes is The following diagram shows an example in which there are 5 nodes in the binary search tree. Given a pointer ROOT to the root node of the binary search tree and an integer k occurring in the INFO field of some node in the tree, write a function that will search the tree for the node N containing the value k, and will then find and turn a pointer to the head node of the class list containing N. So, for example, if ROOT points to the root of the tree above and k 15, the function should return a pointer to HEAD-A. You should assume that a head node is recognisable by the value 9999 in the INFO field. (5 marks) (b) Comment briefly on any disadvantages and/or advantages of using each of the following representations for the class lists instead of the above representation: (i) singly-linked circular lists; (1) singly-linked non-circular lists; (iii) doubly-linked non-circular lists. O. (@) A collection of nodes is arranged as a binary search tree ordered on the he which contains distinct positive integers for each of the mode. In addition to INFO, LLINK and RLINK. each node has three other fields CLASS, SUCC and PRED CLASS is an information field containing a single letter that denotes the class to which the node belongs (there being up to 26 classes). The nodes in each class are arranged as a doubly linked circular list with a list head, by using the pointer fields SUCC and PRED to point to the successor and predecessor of a node in the list, respectively. The format of the nodes is The following diagram shows an example in which there are 5 nodes in the binary search tree. Given a pointer ROOT to the root node of the binary search tree and an integer k occurring in the INFO field of some node in the tree, write a function that will search the tree for the node N containing the value k, and will then find and turn a pointer to the head node of the class list containing N. So, for example, if ROOT points to the root of the tree above and k 15, the function should return a pointer to HEAD-A. You should assume that a head node is recognisable by the value 9999 in the INFO field. (5 marks) (b) Comment briefly on any disadvantages and/or advantages of using each of the following representations for the class lists instead of the above representation: (i) singly-linked circular lists; (1) singly-linked non-circular lists; (iii) doubly-linked non-circular lists
