The following diagram shows an ordered binary tree. Blue Green Indigo Red Orange Violet Yellow

1. (a)A linked list of nodes is used to store the data. Each node consists of a left pointer, the data and a right pointer. -1 is used to represent a null pointer. Complete this linked list to represent the given binary tree. RootPtr LeftPtr Data RightPtr Red Green -1 Blue -1[4]
2. (b)A user-defined record structure is used to store the nodes of the linked list in part (a). Complete the diagram, using your answer for part (a). RootPtr Index LeftPtr Data RightPtr 0 Red 1 Green 2 Yellow 3 Blue 4 Orange 5 Indigo FreePtr 6 Violet 7[4]
3. (c)The linked list in part (a) is implemented using a 1D array of records. Each record contains a left pointer, data and a right pointer. The following pseudocode represents a function that searches for an element in the array of records BinTree. It returns the index of the record if the element is found, or it returns a null pointer if the element is not found. Complete the pseudocode for the function. FUNCTION SearchTree(Item : STRING) NowPtr WHILE NowPtr < -1 IF NowPtr - BinTree [NowPtr].LeftPtr ELSE IF BinTree[NowPtr].Data < Item THEN ELSE RETURN NowPtr ENDIF ENDIF ENDWHILE RETURN NowPtr ENDFUNCTION[4]

This question uses a diagram from the original paper, which isn't shown here. Open the full paper from the past papers archive to see it.