May/June 2026 Paper 43

2026 · 3 questions · 25 parts · 75 marks

0/75 marks
0Correct0Partial0Wrong25Unattempted
Filters0 active

Questions

Select a part to jump to its question

Finish set
Context for question 3
A binary tree is designed to store up to 100 positive integers. The binary tree stores data in ascending numerical order.
The data in the binary tree is created as a global 2D array with the identifier BinaryTree.
Each node has three values:
  • a pointer to the array index with the left node
  • the integer data
  • a pointer to the array index with the right node.
A null pointer is represented by the integer –1. All nodes are initialised with the null data –1.
The table has example data for a binary tree:
indexleft pointerdataright pointer
01202
1410–1
2326–1
3–122–1
4–18–1
The binary tree has two global pointers:
  • TreeRootPointer, initialised to –1, stores the index of the root node of the binary tree
  • FirstFreeNodePointer, initialised to 0, stores the index of the first node that does not store any data.
Data cannot be removed or replaced from the tree. FirstFreeNodePointer is incremented each time a node is added to the binary tree.
3(a)Trees Tree TraversalMedium3 marks
The main program initialises all 100 nodes, TreeRootPointer and FirstFreeNodePointer.
Write program code for the main program.

Answer

0 words
3(b)Trees Tree TraversalHard7 marks
The procedure AddNode():
  • takes an integer parameter to be stored as the data in a new node
  • stores the data in the first element and updates the root pointer when the tree is empty
  • outputs "The tree is full" if the tree is full
  • otherwise stores the data in the next free node, then checks whether the data is less than or greater than the root node, follows the left or right pointer(s) repeatedly until it reaches the appropriate leaf node, and updates the appropriate parent node pointer to the new node.
Write program code for AddNode().

Answer

0 words
3(c)Two Dimensional ArraysEasy2 marks
The procedure OutputArray() outputs the content of the first 10 elements in the binary tree. Each node is output on one line in the format:
text
<left pointer> <data> <right pointer>
For example:
text
1 20 4
Write program code for OutputArray().

Answer

0 words
3(d)(i)Trees Tree TraversalMedium3 marks
Write program code to extend the main program to:
  • take 10 integers as input
  • store each input in the binary tree in the order they are entered using the appropriate procedure
  • output the content of the binary tree using OutputArray().

Answer

0 words
3(d)(ii)Trees Tree TraversalEasy1 mark
Run your extended program. Enter the following numbers in the order shown: 50, 26, 120, 236, 2, 16, 67, 49, 165, 15.
Describe exactly what your program outputs, in the order it is produced.

Answer

0 words
3(e)(i)Trees Tree TraversalHard7 marks
An in-order tree traversal outputs the contents of the binary tree in ascending numerical order by:
  • visiting the left node
  • output the data
  • visiting the right node.
For example, an in-order traversal on the following binary tree will output: 5 12 18 20 26
In this example, the root node holds 20; its left child holds 12 and its right child holds 26; the node holding 12 has a left child holding 5 and a right child holding 18.
The recursive procedure InOrder():
  • takes the root pointer as a parameter
  • makes a recursive call with the left pointer as the parameter if the left pointer is not null
  • outputs the data at the parameter
  • makes a recursive call with the right pointer as the parameter if the right pointer is not null.
Write program code for InOrder().

Answer

0 words
3(e)(ii)Trees Tree TraversalEasy1 mark
Write program code to extend the main program to call InOrder().

Answer

0 words
3(e)(iii)Trees Tree TraversalEasy1 mark
Run your extended program. Enter the following numbers in the order given: 50, 26, 120, 236, 2, 16, 67, 49, 165, 15.
Describe exactly what your program outputs, in the order it is produced.

Answer

0 words