A binary tree consists of nodes. Each node has 3 integer values: a left pointer, data and a right pointer. The binary tree is stored using a global 2D array. The pseudocode declaration for the array is: DECLARE ArrayNodes : ARRAY[0:19, 0:2] OF INTEGER For example: • ArrayNodes[0, 0] stores the left pointer for the first node. • ArrayNodes[0, 1] stores the data for the first node. • ArrayNodes[0, 2] stores the right pointer for the first node. -1 indicates a null pointer, or null data.

1. (a)Write program code to: • declare the global 2D array ArrayNodes • initialise all 3 integer values to -1 for each node.[3]
2. (b)The binary tree stores the following values: Index | Left pointer | Data | Right pointer ---|---|---|--- 0 | 1 | 20 | 5 1 | 2 | 15 | -1 2 | -1 | 3 | 3 3 | -1 | 9 | 4 4 | -1 | 10 | -1 5 | -1 | 58 | -1 6 | -1 | -1 | -1 FreeNode stores the index of the first free element in the array, initialised to 6. RootPointer stores the index of the first node in the tree, initialised to 0. Amend your program by writing program code to store the given data in ArrayNodes and initialise the free node and root node pointers.[2]
3. (c)The following recursive pseudocode function searches the binary tree for a given value. If the value is found, the function must return the index of the value. If the value is not found, the function must return -1. The function is incomplete. There are four incomplete statements. FUNCTION SearchValue (Root : INTEGER, ValueToFind : INTEGER) RETURNS INTEGER IF Root = -1 THEN RETURN -1 ELSE IF ArrayNodes [Root, 1] = ValueToFind THEN RETURN .......................... ELSE IF ArrayNodes[Root, 1] = -1 THEN RETURN -1 ENDIF ENDIF ENDIF IF ArrayNodes[Root, 1] ................... ValueToFind THEN RETURN SearchValue(ArrayNodes[............., 0], ValueToFind) ENDIF IF ArrayNodes[Root, ............] < ValueToFind THEN RETURN SearchValue(ArrayNodes[Root, 2], ValueToFind) ENDIF ENDFUNCTION Write program code for the function SearchValue().[5]
4. (d)A post order traversal performs the following operation: • visit the left node • visit the right node • output the root. For example, in the following tree, the output would be: 3 9 25 60 50 [Figure X.X] An outline of the PostOrder() procedure is: • If left node is not empty, make a recursive call with the left node as the root. • If right node is not empty, make a recursive call with the right node as the root. • Output the current root node. The procedure PostOrder () takes the root node as a parameter. Write program code for the procedure PostOrder().[7]
5. (e)(i)Amend the main program by writing program code to: • call the function SearchValue() to find the position of the number 15 in the tree • use the result from SearchValue() to output either the index of the value if found, or an appropriate message to state that the value was not found • call the procedure PostOrder().[3]
6. (e)(ii)Test your program. Take a screenshot to show the output. Copy and paste the screenshot into part 3(e)(ii) in the evidence document.[1]

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.