A program stores data in a binary tree that is designed using Object-Oriented Programming (OOP). The tree stores data in ascending numerical order, for example: [Diagram of a binary tree]. The class Node stores data about the nodes. NodeData : Integer stores the node's integer data LeftNode : Node stores the node that is stored to the left of the current node, or a null value if there is no node to the left RightNode : Node stores the node that is stored to the right of the current node, or a null value if there is no node to the right Constructor() initialises NodeData to its parameter value; initialises LeftNode and RightNode to a null value GetLeft() returns LeftNode GetRight() returns RightNode GetData() returns NodeData SetLeft() takes an object of type Node as a parameter and stores it in LeftNode SetRight() takes an object of type Node as a parameter and stores it in RightNode

1. (a)(i)Write program code to declare the class Node and its constructor. Do not declare the other methods. Use your programming language appropriate constructor. If you are writing in Python, include attribute declarations using comments.[4]
2. (a)(ii)Write program code for the three get methods.[3]
3. (a)(iii)The method SetLeft() takes an object of type Node as a parameter. The method stores the parameter in the attribute LeftNode The method SetRight() takes an object of type Node as a parameter. The method stores the parameter in the attribute RightNode Write program code for SetLeft() and SetRight()[3]
4. (b)Write the main program to declare five objects of type Node : • Node 1 with the data 10 • Node 2 with the data 20 • Node 3 with the data 5 • Node 4 with the data 15 • Node 5 with the data 7[2]
5. (c)(i)Write program code to declare the class Tree and its constructor. Do not declare the other methods. Use your programming language appropriate constructor. If you are writing in Python, include attribute declarations using comments.[2]
6. (c)(ii)Write program code for GetRootNode()[1]
7. (c)(iii)The method Insert() takes a node as a parameter and then searches the tree to find the position to insert the new node by: • checking whether the node's data is less than or greater than the root node's data • moving to the left node if the data is less than the root node's data • moving to the right node if the data is greater than or equal to the root node's data • repeating until the final position of the node is found and stores the node in that position. Write program code for Insert()[6]
8. (d)The recursive procedure OutputInOrder() outputs the data stored in the binary tree in ascending numerical order. The procedure takes a Node object as a parameter and then: • checks if the left node is null. If there is a left node, the function calls itself with the left node • outputs the data of the current node • checks if the right node is null. If there is a right node, the function calls itself with the right node. Write program code for OutputInOrder()[5]
9. (e)(i)Write program code to extend the main program to: • create a new object of type Tree with the node containing the data 10 as the first node • insert the nodes with the values 20, 5, 15 and 7 into the tree in the order given • call OutputInOrder() with the tree's root node as a parameter.[3]
10. (e)(ii)Test your program. Take a screenshot of the output(s). 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.