An ordered binary tree stores integer data in ascending numerical order. The data for the binary tree is stored in a 2D array with the following structure: LeftPointer Data RightPointer Index [0] [1] [2] [0] 1 10 2 [1] -1 5 -1 [2] -1 16 -1 Each row in the table represents one node on the tree. The number -1 represents a null pointer.

1. (a)The 2D array, ArrayNodes, is declared with space for 20 nodes. Each node has a left pointer, data and right pointer. The program also initialises the: • RootPointer to −1 (null); this points to the first node in the binary tree • FreeNode to 0; this points to the first empty node in the array. Write program code to declare ArrayNodes, RootPointer and FreeNode in the main program. If you are writing in Python programming language, include attribute declarations using comments. Save your program as question 3. Copy and paste the program code into part 3(a) in the evidence document.[4]
2. (b)The procedure AddNode () adds a new node to the array ArrayNodes. The procedure needs to: • take the array, root pointer and free node pointer as parameters • ask the user to enter the data and read this in • add the node to the root pointer if the tree is empty • otherwise, follow the pointers to find the position for the data item to be added • store the data in the location and update all pointers. There are six incomplete statements in the following pseudocode for the procedure AddNode(). PROCEDURE AddNode(BYREF ArrayNodes[] : ARRAY OF INTEGER, BYREF RootPointer : INTEGER, BYREF FreeNode : INTEGER) OUTPUT "Enter the data" INPUT NodeData IF FreeNode <= 19 THEN ArrayNodes[FreeNode, 0] ← -1 ArrayNodes[FreeNode, 1] ← ArrayNodes[FreeNode, 2] ← -1 IF RootPointer = RootPointer ←0 THEN ELSE Placed ← FALSE WHILE Placed = FALSE CurrentNode← RootPointer IF NodeData < ArrayNodes[CurrentNode, 1) THEN IF ArrayNodes[CurrentNode, 0] = -1 THEN ArrayNodes[CurrentNode, 0] ← Placed ← TRUE ELSE CurrentNode ← ArrayNodes[CurrentNode, 0] ENDIF ELSE IF ArrayNodes[CurrentNode, 2] = -1 THEN ArrayNodes[CurrentNode, 2] ← Placed ← ELSE CurrentNode ← ArrayNodes[CurrentNode, 2] ENDIF ENDIF ENDWHILE ENDIF FreeNode ← ELSE OUTPUT("Tree is full") ENDIF ENDPROCEDURE Write program code for the procedure AddNode(). Save your program. Copy and paste the program code into part 3(b) in the evidence document.[8]
3. (c)The procedure PrintAll() outputs the data in each element in ArrayNodes, in the order they are stored in the array. Each element is printed in a row in the order: LeftPointer Data RightPointer For example: 1 20 -1 -1 10 -1 Write program code for the procedure PrintAll(). Save your program. Copy and paste the program code into part 3(c) in the evidence document.[4]
4. (d)(i)The main program should loop 10 times, each time calling the procedure AddNode(). It should then call the procedure PrintAll(). Edit the main program to perform the actions described. Save your program. Copy and paste the program code into part 3(d)(i) in the evidence document.[3]
5. (d)(ii)Test the program by entering the data: 10 5 15 8 12 6 20 11 9 4 Take a screenshot to show the output after the given data are entered. Copy and paste the screenshot into part 3(d)(ii) in the evidence document.[1]
6. (e)(i)An in-order tree traversal visits the left node, then the root (and outputs this), then visits the right node. Write a recursive procedure, InOrder(), to perform an in-order traversal on the tree held in ArrayNodes. Save your program. Copy and paste the program code into part 3(e)(i) in the evidence document.[7]
7. (e)(ii)Test the procedure InOrder() with the same data entered in part (d)(ii). Take a screenshot to show the output after entering the data. 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.