A program stores integers in ascending order in an ordered binary tree. The tree is implemented as a 2D array. Each node is stored with three values: a pointer to the left node the data a pointer to the right node. All null values are stored as -1 The binary tree can store up to 50 nodes. Nodes cannot be deleted from the binary tree. (a) The binary tree is stored as a global array with the identifier TreeArray . The left pointer, the data and the right pointer of each node…

(a) See program code · (b) See program code · (c) See program code · (d) See program code · (e)(i) See program code · (e)(ii) See expected file content

Computer Science 9618/42 — October/November 2025

Cambridge A-Level · Practical · worked solutions for every part, with the mark scheme

questions

marks

150

minutes

Topics Programming Paradigms (Procedural and Object-oriented) · File Processing and Exception Handling · Algorithms and Abstract Data Types · Recursion

Q1Medium-HardProgramming Paradigms (Procedural and Object-oriented)File Processing and Exception Handling

You have been supplied with the following source files:

TreeData.txt

Open the evidence document, evidence.doc

Make sure that your name, centre number and candidate number will appear on every page of this document. This document must contain your answers to each question.

Save this evidence document in your work area as:
evidence_ followed by your centre number_candidate number, for example: evidence_zz999_9999

A class declaration can be used to declare a record. If the programming language used does not support arrays, a list can be used instead.

One source file is used to answer Question 3. The file is called TreeData.txt

A program stores data about birds using Object-Oriented Programming (OOP).

The class Bird stores the data about the birds:

Bird
`DistancePerHour : Real`	stores the number of kilometres per hour (km/h) the bird can fly (between 0.0 and 100.0 inclusive)
`Species : String`	stores the species of the bird, for example Pigeon
`XPosition : Real`	stores the current horizontal position of the bird
`YPosition : Real`	stores the current vertical position of the bird
`Constructor()`	initialises `Species` and `DistancePerHour` to the parameter values; initialises `XPosition` and `YPosition` to 500.0
`GetPosition()`	returns a string message that contains the horizontal and vertical position of the bird
`GetSpecies()`	returns the species of the bird
`Move()`	takes a direction and number of minutes flying (between 0 and 500 inclusive) as parameters and updates the appropriate horizontal or vertical position

(a)

14M

(i)

Write program code to declare the class Bird and its constructor.

Do not declare the other methods.

All attributes should be private.

Use your programming language appropriate constructor.

If you are writing in Python, include attribute declarations using comments.

Save your program as Question1_N25.

Copy and paste the program code into part 1(a)(i) in the evidence document.

4M Similar

DifficultyMedium

Worked solution

Answer

class Bird:
    # __Species: str
    # __DistancePerHour: float
    # __XPosition: float
    # __YPosition: float

    def __init__(self, Species, DistancePerHour):
        self.__Species = Species
        self.__DistancePerHour = DistancePerHour
        self.__XPosition = 500.0
        self.__YPosition = 500.0

Final answer

See program code

Detailed explanation

Background Concept

In Paper 4, an object-oriented class is used to group together data and the methods that act on that data. A constructor is the special method that runs when a new object is created. In Python, the constructor is __init__.

This question also tests encapsulation. Encapsulation means the object's data is kept inside the class and is accessed through methods. In Python, private attributes are usually shown using a double underscore prefix such as __Species. This is the standard way to indicate that the attributes should not be accessed directly from outside the class.

Understanding the Question

You are asked to declare only the class Bird and its constructor. You are specifically told not to declare the other methods yet.

The constructor must:

take parameter values for species and distance per hour
store those values in the object
set both XPosition and YPosition to 500.0
make all attributes private

Because the language here is Python, the question also asks for attribute declarations as comments.

Approach

The simplest correct approach is:

Declare the class Bird.
Add comment lines to show the four attributes.
Write __init__ with parameters for the species and speed.
Assign the parameter values to the private attributes.
Set the two position attributes to the fixed starting value of 500.0.

Step-by-Step Reasoning

class Bird: starts the class declaration.

The comment lines are included because Python does not require attribute declarations in the same way as some other languages. The comments make it clear which attributes exist and what their intended data types are.

def __init__(self, Species, DistancePerHour): defines the constructor. self refers to the current object being created.

self.__Species = Species stores the passed-in species string in the private attribute.

self.__DistancePerHour = DistancePerHour stores the passed-in flying speed.

self.__XPosition = 500.0 and self.__YPosition = 500.0 set the starting coordinates exactly as required by the question. Using 500.0 rather than 500 matches the real-number style in the stem.

No other methods are included because the question explicitly says not to declare them in this part.

Key Takeaways

A constructor sets up an object when it is created.
Encapsulation is shown here by using private attributes.
In Python, attribute comments are often added when the question asks for declarations.
Always initialise every attribute the class description gives you.

Common Mistakes

Making the attributes public, for example using self.Species instead of self.__Species.
Forgetting one of the position attributes.
Setting positions to 0 instead of 500.0.
Writing other methods in this part even though the question says not to.
Misspelling __init__, which would stop Python using it as the constructor.

Things to Be Careful About

Keep the attribute names consistent across later methods.
Use self on every attribute access inside the class.
Use double underscores consistently if you decide the attributes are private.
Keep the parameter names and stored values in the correct order: species first, speed second.

Techniques used

define a class with a language-appropriate constructorstore data in private attributesinitialise attributes from parametersset fixed default coordinate values

(ii)

The method GetSpecies() returns the species of the bird.

Write program code for GetSpecies()

Save your program.

Copy and paste the program code into part 1(a)(ii) in the evidence document.

2M Similar

DifficultyEasy

Worked solution

Answer

def GetSpecies(self):
    return self.__Species

Final answer

See program code

Detailed explanation

Background Concept

A getter method is a method whose job is to return the value of an attribute. Getters are often used in OOP when attributes are private, because code outside the class should not access those attributes directly.

In this case, Species is private, so a method is needed to provide controlled access to it.

Understanding the Question

This part asks for the method GetSpecies() only. The question tells you what it should do: return the species of the bird.

So the method needs no calculation and no input validation. It simply returns the stored species string.

Approach

Because the attribute is already stored inside the object, the method only needs one return statement.

Step-by-Step Reasoning

def GetSpecies(self): defines the method.

return self.__Species sends the private attribute value back to the code that called the method.

Nothing else is needed. There is no formatting, no conversion and no printing. A getter returns a value; it does not display it itself.

Key Takeaways

A getter returns a private attribute.
return gives the value back to the caller.
Getters are part of encapsulation.

Common Mistakes

Using print instead of return. Printing shows the value on screen but does not return it to the caller.
Returning the wrong attribute, such as the speed instead of the species.
Forgetting self. before the attribute name.

Things to Be Careful About

The attribute name must match the constructor exactly.
If the attribute is private, use the private version of the name inside the class.
The method should return just the species, not a message around it.

Techniques used

define a getter methodreturn a private attribute directly

(iii)

The method GetPosition() returns a string of the bird's data in the format:

"X = " & <XPosition> & " Y = " & <YPosition>"

An example string for a bird is:

X = 500.0 Y = 250.0

Write program code for GetPosition()

Save your program.

Copy and paste the program code into part 1(a)(iii) in the evidence document.

3M Similar

DifficultyMedium-Easy

Worked solution

Answer

def GetPosition(self):
    return "X = " + str(self.__XPosition) + " Y = " + str(self.__YPosition)

Final answer

See program code

Detailed explanation

Background Concept

A method can return a formatted string built from several pieces of data. When numbers are included in a string in Python, they usually need to be converted to strings first unless you use a formatting feature such as an f-string.

This question is about combining labels and stored attribute values into one message.

Understanding the Question

The method GetPosition() must return a string in a very specific format:
X = <XPosition> Y = <YPosition>

That means the method should not return two separate values, and it should not print the result directly. It must return one string containing both coordinates in the required order.

Approach

Use string concatenation:

start with "X = "
add the X position converted to a string
add " Y = "
add the Y position converted to a string

Step-by-Step Reasoning

def GetPosition(self): defines the method.

"X = " is the fixed label for the horizontal coordinate.

str(self.__XPosition) converts the real value into text so it can be joined into the message.

" Y = " is the fixed separator and label for the vertical coordinate.

str(self.__YPosition) converts the Y coordinate into text.

The full result is returned as one string. For example, if __XPosition is 500.0 and __YPosition is 250.0, the returned value becomes exactly:
X = 500.0 Y = 250.0

Key Takeaways

Return the whole message as one string.
Convert number values to strings when concatenating.
Follow the exact required output format.

Common Mistakes

Printing the position instead of returning it.
Omitting one of the labels such as X = or Y =.
Returning the coordinates in the wrong order.
Forgetting to convert the real values to strings when using concatenation.

Things to Be Careful About

The spaces in the format matter if the output is being checked visually.
Use the current stored positions, not hard-coded values.
Keep the method name and attribute names consistent with the rest of the class.

Techniques used

define a method that returns a stringconcatenate labels with attribute valuesconvert numeric values to strings

(iv)

If the bird is travelling north, the vertical position increases. If the bird is travelling south, the vertical position decreases.

If the bird is travelling east, the horizontal position increases. If the bird is travelling west, the horizontal position decreases.

The method Move():

takes the direction of travel as a parameter in the form 'N' for north, 'S' for south, 'E' for east or 'W' for west
takes the number of minutes that the bird has been flying (to the nearest minute) as a parameter
calculates the distance travelled by the bird using the formula:
distance travelled = (distance per hour/60) * minutes flying
updates the vertical or horizontal position using the distance calculated.

You do not need to validate the parameters.

Write program code for Move()

Save your program.

Copy and paste the program code into part 1(a)(iv) in the evidence document.

5M Similar

DifficultyMedium

Worked solution

Answer

def Move(self, Direction, Minutes):
    DistanceTravelled = (self.__DistancePerHour / 60) * Minutes

    if Direction == "N":
        self.__YPosition = self.__YPosition + DistanceTravelled
    elif Direction == "S":
        self.__YPosition = self.__YPosition - DistanceTravelled
    elif Direction == "E":
        self.__XPosition = self.__XPosition + DistanceTravelled
    else:
        self.__XPosition = self.__XPosition - DistanceTravelled

Final answer

See program code

Detailed explanation

Background Concept

A position can be represented using coordinates. In this question, XPosition is the horizontal position and YPosition is the vertical position.

Movement rules are:

north increases Y
south decreases Y
east increases X
west decreases X

The distance moved is calculated from speed and time. If the speed is in kilometres per hour and the time is in minutes, first divide the hourly speed by 60 to get kilometres per minute, then multiply by the number of minutes.

Understanding the Question

The Move() method receives two parameters:

a direction: N, S, E or W
the number of minutes flown

You are told not to validate these parameters in this method, so you can assume they are already valid. Your task is to calculate how far the bird travels and then update the correct coordinate in the correct direction.

Approach

The method naturally breaks into two stages:

Calculate the distance travelled.
Use an if / elif / else structure to decide which coordinate to change and whether to add or subtract.

Because only four directions are possible, a simple chain of conditions is enough.

Step-by-Step Reasoning

DistanceTravelled = (self.__DistancePerHour / 60) * Minutes converts the bird's stored speed from per hour to per minute, then multiplies by the flying time.

Example: if the speed is 71.0 km/h and the bird flies for 60 minutes:

71.0 / 60 gives the distance per minute
multiplying by 60 gives 71.0 km travelled

Then the direction is checked:

If Direction == "N", the bird goes north, so YPosition increases.
If Direction == "S", the bird goes south, so YPosition decreases.
If Direction == "E", the bird goes east, so XPosition increases.
Otherwise, the remaining valid direction is west, so XPosition decreases.

Only one coordinate changes for each move.

Key Takeaways

Convert units carefully before updating coordinates.
North/south affect Y; east/west affect X.
Add for north/east and subtract for south/west.

Common Mistakes

Updating the wrong coordinate, such as changing X for north.
Adding when you should subtract, especially for south and west.
Forgetting to divide by 60 before multiplying by minutes.
Replacing the position with the distance instead of adding or subtracting from the current position.

Things to Be Careful About

Use the stored speed attribute, not a passed-in speed parameter.
Keep the direction letters exactly as expected.
Since validation is not required here, the method can assume the caller supplies only valid directions.
Make sure the calculation happens before the selection so the same distance value can be reused.

Techniques used

calculate distance from speed and timeuse selection to handle four directionsupdate the correct coordinate by addition or subtraction

(b)

The main program creates two instances of Bird

The first bird is the species 'Cockatiel' and flies 71.0km/h.

The second bird is the species 'Macaw' and flies 56.0km/h.

Write program code to declare and initialise the two birds.

Save your program.

Copy and paste the program code into part 1(b) in the evidence document.

3M Similar

DifficultyMedium-Easy

Worked solution

Answer

Bird1 = Bird("Cockatiel", 71.0)
Bird2 = Bird("Macaw", 56.0)

Final answer

See program code

Detailed explanation

Background Concept

Once a class has been defined, objects are created by calling the constructor. Each object gets its own copy of the attributes. Here, each Bird object stores its own species, speed and position.

Understanding the Question

The main program must create two bird objects:

one for Cockatiel with flying speed 71.0
one for Macaw with flying speed 56.0

The values must be passed to the constructor in the correct order.

Approach

Use the class name Bird followed by brackets containing the species and the speed.

Step-by-Step Reasoning

Bird1 = Bird("Cockatiel", 71.0) creates the first object. The constructor stores:

Species as Cockatiel
DistancePerHour as 71.0
positions as 500.0 and 500.0

Bird2 = Bird("Macaw", 56.0) does the same for the second object.

The variable names can be chosen by the programmer, but they must refer to two separate instances.

Key Takeaways

Creating an object calls the constructor.
Each instance stores different data values.
Constructor arguments must match the required order and data type.

Common Mistakes

Reversing the constructor parameters.
Creating only one object instead of two.
Using integer 71 or 56 if the task expects real values written as 71.0 and 56.0.

Things to Be Careful About

Keep the species spellings exact.
Make sure the objects are stored in different variables.
The constructor already sets the starting positions, so no extra position assignments are needed here.

Techniques used

instantiate objects from a classpass constructor arguments in the required order

(c)

11M

(i)

The main program needs to:

output a message that includes the species and current X position and Y position for each bird
prompt the user to select one of the birds to move and take this as an input
prompt the user to enter the direction the bird has been travelling and take this as an input
prompt the user to enter the time to the nearest minute that the bird has been travelling and take this as an input
call the appropriate method to update the chosen bird's position
output an update on the bird's new position.

Each input needs to repeat until valid data is entered. All outputs must be meaningful.

Write program code to amend the main program.

Save your program.

Copy and paste the program code into part 1(c)(i) in the evidence document.

8M Similar

DifficultyMedium-Hard

Worked solution

Answer

print("Current position for " + Bird1.GetSpecies() + ": " + Bird1.GetPosition())
print("Current position for " + Bird2.GetSpecies() + ": " + Bird2.GetPosition())

Choice = ""
while Choice not in ["1", "2"]:
    Choice = input("Select bird to move (1=Cockatiel, 2=Macaw): ")
    if Choice not in ["1", "2"]:
        print("Please enter 1 or 2.")

Direction = ""
while Direction not in ["N", "S", "E", "W"]:
    Direction = input("Enter direction (N/S/E/W): ").upper()
    if Direction not in ["N", "S", "E", "W"]:
        print("Please enter N, S, E or W.")

Valid = False
while not Valid:
    try:
        Minutes = int(input("Enter minutes flying (0 to 500): "))
        if 0 <= Minutes <= 500:
            Valid = True
        else:
            print("Please enter a value from 0 to 500.")
    except ValueError:
        print("Please enter a whole number.")

if Choice == "1":
    Bird1.Move(Direction, Minutes)
    print("New position for " + Bird1.GetSpecies() + ": " + Bird1.GetPosition())
else:
    Bird2.Move(Direction, Minutes)
    print("New position for " + Bird2.GetSpecies() + ": " + Bird2.GetPosition())

Final answer

See program code

Detailed explanation

Background Concept

A main program often coordinates object method calls and user interaction. In a task like this, the class already knows how to store data and update itself, while the main program is responsible for:

displaying information
getting input
validating input
choosing which object should respond

Validation means checking that the input is acceptable before using it. Repetition is used so the prompt continues until valid data is entered. In Python, try / except is commonly used to prevent a run-time error when converting user input to an integer.

Understanding the Question

This part does not ask you to change the class again. It asks you to amend the main program so that it:

shows both birds and their current positions
asks the user which bird to move
asks for direction
asks for the number of minutes
repeats each input until it is valid
calls Move() for the chosen bird
outputs the updated position

The key clues are “repeat until valid data is entered” and “call the appropriate method”. That means this is a validation-and-control-flow task, not a new class-design task.

Approach

The best structure is:

Output the current position of each bird by calling GetSpecies() and GetPosition().
Validate a bird choice of 1 or 2.
Validate a direction of N, S, E or W.
Validate the minutes as a whole number in the range 0 to 500.
Use the bird choice to decide whether to call Move() on Bird1 or Bird2.
Output the chosen bird's new position.

Each validation is done with a loop so the user stays at that step until the input is correct.

Step-by-Step Reasoning

The first two print statements display the initial state of both birds. The methods are used instead of direct attribute access because the attributes are private.

For the bird selection, Choice starts as an invalid empty string. The loop continues while the value is not "1" or "2". If the user enters anything else, a helpful message is shown.

For the direction, the program again starts with an empty value and repeats until the direction is one of the allowed codes. .upper() is useful because it allows the user to type n or w and still have it accepted as N or W.

For the minutes, the program must check two things:

the input must be a whole number
it must be between 0 and 500 inclusive

int(input(...)) may fail if the user types letters or a decimal value, so it is placed inside a try block. If conversion fails, ValueError is caught and the program asks again instead of crashing.

Once all inputs are valid, the chosen bird is moved. If Choice is "1", call Bird1.Move(Direction, Minutes). Otherwise call Bird2.Move(Direction, Minutes).

Finally, the program prints the new position for the bird that moved. Again, the output uses GetSpecies() and GetPosition().

Key Takeaways

Main programs often coordinate object use rather than storing the data themselves.
Validation loops keep asking until acceptable input is given.
try / except prevents crashes during numeric conversion.
OOP methods should be called on the correct object based on user choice.

Common Mistakes

Forgetting to repeat on invalid input.
Validating direction but not converting lower-case input.
Accepting minutes outside the range 0 to 500.
Calling Move() on the wrong bird regardless of the user's choice.
Printing only the updated bird and forgetting the initial positions for both birds.
Accessing private attributes directly instead of using methods.

Things to Be Careful About

The bird choice in this solution is validated as strings because input() returns a string.
The minutes check is inclusive, so both 0 and 500 are valid.
Use meaningful prompts and error messages because the question explicitly asks for meaningful outputs.
Make sure only the selected bird is moved; the other bird should remain unchanged.
Keep the output format consistent so the test outputs are easy to verify.

Techniques used

output object data using methodsvalidate menu input with repetitionvalidate direction input against a fixed set of codesuse exception handling to validate numeric inputcall a method on the chosen object and display the updated result

(ii)

Test your program four times to meet these criteria:

Test 1: The Cockatiel travels north for 60 minutes.

Test 2: The Macaw travels south for 30 minutes.

Test 3: The Cockatiel travels west for 30 minutes.

Test 4: The Macaw travels east for 60 minutes.

Take a screenshot of the output(s).

Save your program.

Copy and paste the screenshot(s) into part 1(c)(ii) in the evidence document.

3M Similar

DifficultyMedium-Easy

Worked solution

Answer

If the program is run from the initial positions each time, the expected outputs are:

Test 1 inputs: 1, N, 60
Current position for Cockatiel: X = 500.0 Y = 500.0
Current position for Macaw: X = 500.0 Y = 500.0
Select bird to move (1=Cockatiel, 2=Macaw): 1
Enter direction (N/S/E/W): N
Enter minutes flying (0 to 500): 60
New position for Cockatiel: X = 500.0 Y = 571.0

Test 2 inputs: 2, S, 30
Current position for Cockatiel: X = 500.0 Y = 500.0
Current position for Macaw: X = 500.0 Y = 500.0
Select bird to move (1=Cockatiel, 2=Macaw): 2
Enter direction (N/S/E/W): S
Enter minutes flying (0 to 500): 30
New position for Macaw: X = 500.0 Y = 472.0

Test 3 inputs: 1, W, 30
Current position for Cockatiel: X = 500.0 Y = 500.0
Current position for Macaw: X = 500.0 Y = 500.0
Select bird to move (1=Cockatiel, 2=Macaw): 1
Enter direction (N/S/E/W): W
Enter minutes flying (0 to 500): 30
New position for Cockatiel: X = 464.5 Y = 500.0

Test 4 inputs: 2, E, 60
Current position for Cockatiel: X = 500.0 Y = 500.0
Current position for Macaw: X = 500.0 Y = 500.0
Select bird to move (1=Cockatiel, 2=Macaw): 2
Enter direction (N/S/E/W): E
Enter minutes flying (0 to 500): 60
New position for Macaw: X = 556.0 Y = 500.0

Final answer

See expected console output

Detailed explanation

Background Concept

Testing a practical program means choosing known inputs and checking that the outputs match what the logic should produce. Here the important logic is the movement rule:

north increases Y
south decreases Y
east increases X
west decreases X

The distance travelled is calculated using:
(distance per hour / 60) * minutes

When testing, it is important to know whether each test starts from a fresh run or continues from the previous test. In most exam practical evidence, each named test is usually shown clearly, often from a fresh run, unless the candidate deliberately demonstrates cumulative state.

Understanding the Question

You are told exactly which four tests to perform. So the job is not to invent tests, but to run the finished program using those inputs and show the resulting output.

To work out the expected output, assume each test starts with both birds at:

X = 500.0
Y = 500.0

Then calculate the new position for the chosen bird only.

Approach

For each test:

Identify the bird and its speed.
Calculate the distance travelled.
Decide which coordinate changes.
Add or subtract the distance.
Keep the other coordinate unchanged.

Step-by-Step Reasoning

Test 1: Cockatiel, north, 60 minutes.

Cockatiel speed = 71.0 km/h
distance = (71.0 / 60) * 60 = 71.0
north means increase Y
new position = X = 500.0, Y = 571.0

Test 2: Macaw, south, 30 minutes.

Macaw speed = 56.0 km/h
distance = (56.0 / 60) * 30 = 28.0
south means decrease Y
new position = X = 500.0, Y = 472.0

Test 3: Cockatiel, west, 30 minutes.

Cockatiel speed = 71.0 km/h
distance = (71.0 / 60) * 30 = 35.5
west means decrease X
new position = X = 464.5, Y = 500.0

Test 4: Macaw, east, 60 minutes.

Macaw speed = 56.0 km/h
distance = (56.0 / 60) * 60 = 56.0
east means increase X
new position = X = 556.0, Y = 500.0

These calculated positions are the key values that should appear in the screenshots.

Key Takeaways

Good tests check different branches of the code.
Expected outputs can be calculated by hand before running the program.
When objects start from the same initial state, each fresh run is easy to verify.

Common Mistakes

Carrying forward the previous test's final position into the next test when the program was meant to be restarted.
Updating the wrong coordinate for a direction.
Using the wrong bird's speed in the calculation.
Forgetting that 30 minutes is half an hour, so the distance is half the hourly speed.

Things to Be Careful About

Be consistent about whether each test is a fresh run. The outputs shown here assume a fresh run each time.
If you run all four tests in one continuous session without restarting, later outputs will be different because the positions will already have changed.
The screenshot evidence should clearly show the entered inputs and the final output for each test.

Techniques used

run the program with supplied test inputscalculate new coordinates from speed and timecheck direction-based coordinate updates

Q2Medium-HardProgramming Paradigms (Procedural and Object-oriented)Algorithms and Abstract Data TypesRecursion

A program stores 20 unique random integers between 0 and 100 (inclusive) in a 1D array that is local to the main program.

(a)

Write program code to declare the array local to the main program and store 20 unique random numbers between 0 and 100 (inclusive) in the array.

Save your program as Question2_N25.

Copy and paste the program code into part 2(a) in the evidence document.

3M Similar

DifficultyMedium

Worked solution

Answer

import random

def main():
    numbers = []
    while len(numbers) < 20:
        value = random.randint(0, 100)
        if value not in numbers:
            numbers.append(value)

Final answer

See program code

Detailed explanation

Background Concept

In Paper 4, an "array" in Python is normally represented using a list. If the question says the array is local to the main program, that means it should be created inside main() rather than as a global variable. The other key idea here is uniqueness: every stored value must be different. A common way to achieve this is to keep generating random values and only store a value if it is not already present in the list.

Understanding the Question

You are asked to write code that creates a list for 20 integers and fills it with random numbers from 0 to 100 inclusive. The word unique is the important clue: you cannot simply generate 20 random values and store them directly, because duplicates might occur. The list must be local to the main program, so it should be declared inside main().

Approach

A straightforward method is:

Create an empty list inside main().
Repeatedly generate a random integer with random.randint(0, 100).
Check whether that integer is already in the list.
If it is not present, append it.
Stop once the list contains 20 items.

This method is simple, readable and guarantees uniqueness.

Step-by-Step Reasoning

import random is needed so that Python can generate random numbers.

Inside main(), numbers = [] creates an empty list. Because it is inside the function, it is local to that function.

The condition while len(numbers) < 20: keeps the loop running until exactly 20 values have been stored.

value = random.randint(0, 100) generates one candidate integer. The bounds are inclusive, so both 0 and 100 are possible.

if value not in numbers: checks whether that candidate has already been stored. If it is new, numbers.append(value) adds it to the list. If it is already present, nothing is added and the loop simply tries again.

Eventually the list reaches length 20, so the loop stops. At that point the program has exactly 20 integers, all within the correct range, and all unique.

Key Takeaways

A local array/list in Python should be created inside the function that owns it.
To guarantee unique random values, generate a candidate and only store it if it is not already present.
random.randint(a, b) includes both endpoints.

Common Mistakes

Declaring the list globally instead of inside main().
Using for to generate exactly 20 random values without checking for duplicates.
Using the wrong bounds, such as random.randint(1, 100), which would exclude 0.
Forgetting to import the random module.

Things to Be Careful About

Make sure the loop condition is based on the current number of stored items, not the number of random attempts made. Also be careful that not in is checking the existing list contents before appending. In Python, this solution uses 0-based indexing implicitly, but no direct indexing is needed yet.

Techniques used

declare a local array inside the main proceduregenerate random integers in the required rangetest for duplicates before appending to the array

(b)

The procedure PrintArray() takes an integer array as a parameter. The procedure outputs the array contents on a single line with a space between each integer.

Write the program code for PrintArray()

Save your program.

Copy and paste the program code into part 2(b) in the evidence document.

3M Similar

DifficultyMedium-Easy

Worked solution

Answer

def PrintArray(ArrayData):
    for Item in ArrayData:
        print(Item, end=" ")
    print()

Final answer

See program code

Detailed explanation

Background Concept

A procedure is a named block of code that performs a task. Here, the task is to output every value in an integer array. When an array is passed as a parameter, the procedure can process each element in turn using a loop. The phrase "on a single line with a space between each integer" tells you that the output must stay on one line rather than printing each value on a separate line.

Understanding the Question

The question gives the procedure name PrintArray() and says it takes an integer array as a parameter. Its job is only to display the contents. So the key requirements are:

accept the array as a parameter
visit every element
output all values on one line
separate values with spaces

Approach

Use a loop to go through the parameter one item at a time. In Python, print(..., end=" ") keeps output on the same line and adds a space after each item. After the loop, a final print() moves to the next line so later output starts neatly.

Step-by-Step Reasoning

def PrintArray(ArrayData): defines the procedure and gives it one parameter, the array to print.

for Item in ArrayData: is a simple traversal of the whole list. This works for arrays of any length because it automatically visits every element.

print(Item, end=" ") outputs the current integer and leaves the cursor on the same line. The end=" " replaces Python's normal newline with a space.

After the loop, print() outputs a newline. Without this final statement, the next message printed by the program would continue on the same line as the array.

Key Takeaways

A procedure can take an array parameter and process all its elements.
A loop is the standard way to traverse an array.
In Python, end=" " is useful when you need multiple values on one line.

Common Mistakes

Printing each number with a normal print() so every value appears on a separate line.
Forgetting the final print(), which can spoil the formatting of later output.
Not using the parameter and instead trying to access a global list.

Things to Be Careful About

The procedure should work for any array passed to it, not just the one created in main(). Also keep the function name exactly as given: PrintArray. In exam practical work, losing marks often comes from small naming mistakes or poor formatting rather than the loop logic itself.

Techniques used

define a procedure with an array parametertraverse the array with a loopformat output on one line with spaces between values

(c)

The function BubbleSort():

takes an integer array as a parameter
sorts the data into ascending order using a bubble sort
returns the sorted array.

The function needs to work for an array of any length.

Do not use an inbuilt sorting method.

Write program code for BubbleSort()

Save your program.

Copy and paste the program code into part 2(c) in the evidence document.

5M Similar

DifficultyMedium

Worked solution

Answer

def BubbleSort(ArrayData):
    SortedArray = ArrayData[:]
    n = len(SortedArray)

    for Pass in range(n - 1):
        for Index in range(0, n - Pass - 1):
            if SortedArray[Index] > SortedArray[Index + 1]:
                SortedArray[Index], SortedArray[Index + 1] = SortedArray[Index + 1], SortedArray[Index]

    return SortedArray

Final answer

See program code

Detailed explanation

Background Concept

Bubble sort is a simple comparison sort. It repeatedly works through the array, compares adjacent items and swaps them if they are in the wrong order. After one full pass, the largest remaining value has "bubbled" to the end. After each pass, one more value is guaranteed to be in its final position, so the inner loop can become shorter.

Understanding the Question

The function must:

be called BubbleSort()
take an integer array as a parameter
sort into ascending order
return the sorted array
work for an array of any length
not use an inbuilt sorting method

So this is not just "make the array sorted somehow". The method itself must be bubble sort.

Approach

Use two loops:

the outer loop controls how many passes are made
the inner loop compares neighbouring elements on that pass

If an element is larger than the one after it, swap them. To keep the original parameter unchanged, first make a copy of the list and sort that copy.

Step-by-Step Reasoning

def BubbleSort(ArrayData): defines the function.

SortedArray = ArrayData[:] creates a shallow copy of the input list. That means the function returns a sorted version without relying on the caller to know that the original list was modified.

n = len(SortedArray) stores the array length so the algorithm works for any size.

for Pass in range(n - 1): performs enough passes to guarantee the list is sorted.

Inside that, for Index in range(0, n - Pass - 1): compares adjacent pairs. The - Pass - 1 part matters because the largest items have already moved to the end on earlier passes, so those positions do not need checking again.

if SortedArray[Index] > SortedArray[Index + 1]: tests whether the pair is in the wrong order for ascending sort.

SortedArray[Index], SortedArray[Index + 1] = ... swaps the two values.

After all passes are complete, return SortedArray sends the sorted array back to the caller.

Key Takeaways

Bubble sort repeatedly swaps adjacent out-of-order values.
The inner loop gets shorter after each pass because the end section is already sorted.
If a function is required to return a sorted array, remember to return it explicitly.

Common Mistakes

Using Python's inbuilt .sort() or sorted() when the question specifically forbids it.
Getting the inner loop bound wrong and causing an index error.
Forgetting to return the sorted array.
Sorting in descending order by using the wrong comparison.

Things to Be Careful About

Be precise with range(0, n - Pass - 1). If you use n - Pass, then Index + 1 can go out of range. Also remember that Python uses 0-based indexing, so the last valid position is n - 1. If your main program expects a returned array, you must assign the function result back to a variable.

Techniques used

copy the input array before sortinguse nested loops for bubble sort passescompare adjacent elements and swap when out of orderreturn the sorted array

(d)

(i)

The main program:

outputs the contents of the array using PrintArray()
sorts the array using BubbleSort()
outputs "Sorted"
outputs the contents of the sorted array using PrintArray()

Write program code for the main program.

Save your program.

Copy and paste the program code into part 2(d)(i) in the evidence document.

3M Similar

DifficultyMedium-Easy

Worked solution

Answer

import random

def main():
    numbers = []
    while len(numbers) < 20:
        value = random.randint(0, 100)
        if value not in numbers:
            numbers.append(value)

    PrintArray(numbers)
    numbers = BubbleSort(numbers)
    print("Sorted")
    PrintArray(numbers)

main()

Final answer

See program code

Detailed explanation

Background Concept

The main program is where the separate parts of a procedural solution are brought together in the correct order. A procedure such as PrintArray() performs an action, while a function such as BubbleSort() returns a value. In a complete program, one common skill is knowing when to call each and how to use the returned result.

Understanding the Question

This part tells you exactly what the main program must do:

output the current array
sort the array using BubbleSort()
output the word Sorted
output the sorted array

Because the array from part (a) is local to the main program, the main program must also contain the code that creates and fills it.

Approach

Build main() so it first creates the list of 20 unique random numbers. Then call PrintArray(numbers) to show the unsorted values. Next, call BubbleSort(numbers) and store the returned sorted list back into numbers. Finally, print the label Sorted and display the sorted list.

Step-by-Step Reasoning

The first part of main() is the same local-list creation from part (a). This guarantees numbers exists inside main() and contains 20 unique integers.

PrintArray(numbers) outputs the original order of the list.

numbers = BubbleSort(numbers) is important. Since the function returns the sorted array, the result must be assigned back to a variable. Here it replaces the old unsorted version.

print("Sorted") provides the required heading between the two outputs.

The final PrintArray(numbers) prints the list again, but now in ascending order.

main() at the end actually runs the program.

Key Takeaways

Procedures are called for actions; functions are called when you need a returned result.
The main program should follow the required sequence exactly.
If a function returns a processed array, assign that result back to a variable.

Common Mistakes

Calling BubbleSort(numbers) without storing the returned list.
Printing Sorted before the first array output instead of between the two arrays.
Forgetting to call main() so nothing runs.

Things to Be Careful About

Keep the array local to main(). Also ensure the second call to PrintArray() happens after sorting, not before. In practical questions, correct ordering of statements is often what earns the marks.

Techniques used

call a procedure to display an arraycall a function and store its returned arraysequence output and processing steps in the main program

(ii)

Test your program.

Take a screenshot of the output(s).

Save your program.

Copy and paste the screenshot(s) into part 2(d)(ii) in the evidence document.

1M Similar

DifficultyEasy

Worked solution

Answer

Example valid output (values will vary because the array is random):

57 3 88 21 64 0 45 72 19 100 34 8 61 27 93 14 50 76 39 6
Sorted
0 3 6 8 14 19 21 27 34 39 45 50 57 61 64 72 76 88 93 100

Final answer

See example output

Detailed explanation

Background Concept

Testing a program means running it and checking whether the observed output matches what the algorithm is supposed to do. For a sorting task, one obvious check is that the first output is the original unsorted data and the second output is the same values rearranged into ascending order.

Understanding the Question

This part does not ask for more code. It asks for evidence that the program from earlier parts has been run successfully. Because the numbers are random, there is no single fixed output. What matters is that the screenshot shows:

one line of 20 unique integers
the word Sorted
the same 20 integers in ascending order on the next line

Approach

Run the program once. Capture the output. Then check that the sorted line contains exactly the same numbers as the first line, but ordered from smallest to largest.

Step-by-Step Reasoning

The example shown in the answer is only one possible run. Since the list is random, your actual values will usually be different.

In the example, the first line is the unsorted list. The second line is simply the label Sorted. The third line is the sorted version.

To verify correctness, check that:

there are still 20 values
no values have been lost or duplicated during sorting
the final line increases from left to right

If all of these are true, the screenshot is valid evidence for this part.

Key Takeaways

For random-data tasks, testing focuses on the pattern of correct behaviour, not one fixed result.
A correct sort preserves all original values and only changes their order.

Common Mistakes

Submitting output that shows only the sorted list and not the original list.
Forgetting to include the Sorted line.
Using output where the final line is not fully in ascending order.

Things to Be Careful About

Because values are random, your screenshot will not match anyone else's exactly. That is fine. What matters is that the format matches the task and that the sorted line is correct for the generated data.

Techniques used

run the completed programobserve unsorted and sorted outputverify that the second line is in ascending order

(e)

The recursive function RecursiveBinarySearch() takes four parameters:

an integer array
the lower bound of the array
the upper bound of the array
the value to find in the array.

The recursive function performs a binary search to find the index of the value in the array.

The function returns the index of the value if it is found. The function returns -1 if the value is not found.

Write program code for RecursiveBinarySearch()

Save your program.

Copy and paste the program code into part 2(e) in the evidence document.

6M Similar

DifficultyMedium-Hard

Worked solution

Answer

def RecursiveBinarySearch(ArrayData, LowerBound, UpperBound, ValueToFind):
    if LowerBound > UpperBound:
        return -1

    Middle = (LowerBound + UpperBound) // 2

    if ArrayData[Middle] == ValueToFind:
        return Middle
    elif ArrayData[Middle] < ValueToFind:
        return RecursiveBinarySearch(ArrayData, Middle + 1, UpperBound, ValueToFind)
    else:
        return RecursiveBinarySearch(ArrayData, LowerBound, Middle - 1, ValueToFind)

Final answer

See program code

Detailed explanation

Background Concept

Binary search is a searching algorithm for sorted arrays. Instead of checking every element one by one, it repeatedly looks at the middle element and decides whether the target must be in the lower half or the upper half. A recursive version solves the smaller subproblem by calling itself with new bounds.

A recursive routine needs a base case. Without it, the function would keep calling itself forever. In binary search, the base case for "not found" is when the lower bound moves past the upper bound.

Understanding the Question

The function RecursiveBinarySearch() must take four parameters:

the integer array
the lower bound
the upper bound
the value to find

It must return the index if the value is found, or -1 if it is not found. Since this is binary search, the array must already be sorted before this function is used.

Approach

Use the classic recursive pattern:

If the current search range is invalid, return -1.
Find the middle index.
If the middle element equals the target, return that index.
If the target is larger, search the upper half.
Otherwise, search the lower half.

Each recursive call works on a smaller portion of the array, so the search eventually ends.

Step-by-Step Reasoning

def RecursiveBinarySearch(ArrayData, LowerBound, UpperBound, ValueToFind): defines the function with the required four parameters.

The first test is if LowerBound > UpperBound:. This means there is no valid range left to search, so the value is not present. The function returns -1.

Middle = (LowerBound + UpperBound) // 2 finds the midpoint using integer division. In Python, // is needed so that the result is an integer index.

If ArrayData[Middle] == ValueToFind, the search is successful and the function returns Middle.

If the middle value is smaller than the target, the target can only be in the upper half of a sorted array. So the function calls itself with Middle + 1 as the new lower bound.

Otherwise, the target must be in the lower half, so the function calls itself with Middle - 1 as the new upper bound.

Because each call halves the search area, this is much more efficient than a linear search on large sorted arrays.

Key Takeaways

Binary search only works correctly on sorted data.
A recursive solution needs both a base case and a recursive case.
Returning the result of the recursive call is essential; otherwise the found index would be lost.

Common Mistakes

Forgetting the base case LowerBound > UpperBound.
Using / instead of //, which would produce a non-integer midpoint in Python.
Recursing into the wrong half after the comparison.
Searching an unsorted array.

Things to Be Careful About

Use len(array) - 1 as the initial upper bound later in the main program, not len(array). Also remember that the function returns an index, not the value itself. In Python, indexes are 0-based, so the first element is at position 0.

Techniques used

write a recursive base case for failurecalculate the midpoint of the current search rangecompare the target with the midpoint valuerecurse into the lower or upper half accordingly

(f)

(i)

The main program:

prompts the user to enter an integer
takes the integer as input
calls RecursiveBinarySearch() with the sorted array, appropriate lower bound, appropriate upper bound and the user's input as parameters
outputs "Not found" if the input is not within the array
outputs "Found at position" and the index if the input is within the array.

Write program code to amend the main program.

Save your program.

Copy and paste the program code into part 2(f)(i) in the evidence document.

3M Similar

DifficultyMedium-Easy

Worked solution

Answer

Add these lines to main() after the sorted array has been output:

    SearchValue = int(input("Enter an integer: "))
    Index = RecursiveBinarySearch(numbers, 0, len(numbers) - 1, SearchValue)

    if Index == -1:
        print("Not found")
    else:
        print("Found at position", Index)

Final answer

See program code

Detailed explanation

Background Concept

After writing separate functions, the main program must supply the correct arguments and handle the returned value properly. For binary search, the bounds passed to the function are especially important: the lower bound is the first valid index and the upper bound is the last valid index.

Understanding the Question

This part asks you to extend the main program so that it:

asks the user for an integer
calls RecursiveBinarySearch() on the sorted array
outputs Not found if the function returns -1
otherwise outputs Found at position and the index

The key detail is that the array passed into the search must be the sorted one, not the original unsorted version.

Approach

Read the input with int(input(...)), call the search function using bounds 0 and len(numbers) - 1, then use an if statement to decide which message to print.

Step-by-Step Reasoning

SearchValue = int(input("Enter an integer: ")) displays a prompt and converts the typed value into an integer.

Index = RecursiveBinarySearch(numbers, 0, len(numbers) - 1, SearchValue) calls the recursive function. Since numbers has already been sorted in the main program, it is ready for binary search. The first index is 0 and the last index is len(numbers) - 1.

If the function returns -1, the number is not present, so print("Not found") is used.

Otherwise the number exists in the array, and print("Found at position", Index) outputs the required message and its position.

Key Takeaways

Binary search must be called on sorted data.
The correct initial bounds for a Python list are 0 and len(list) - 1.
A search function often uses a special return value such as -1 to mean failure.

Common Mistakes

Calling the search on the unsorted list.
Using len(numbers) as the upper bound instead of len(numbers) - 1.
Forgetting to convert the input to an integer.
Testing the wrong condition, such as if Index == 0: for not found.

Things to Be Careful About

This code is an amendment to main(), so it must be placed after the array has been sorted. Also remember that the reported position is the Python index, which starts at 0 unless the question says otherwise.

Techniques used

prompt for and read integer inputcall the recursive binary search with correct boundstest the returned index against the not-found valueoutput a message based on the search result

(ii)

Test your program three times with each of the inputs described:

Test 1: the smallest number in the array

Test 2: the largest number in the array

Test 3: a number not in the array

Take a screenshot of each output.

Save your program.

Copy and paste the screenshot(s) into part 2(f)(ii) in the evidence document.

2M Similar

DifficultyEasy

Worked solution

Answer

Example valid outputs for the sample sorted array shown in part 2(d)(ii):

Test 1
Enter an integer: 0
Found at position 0

Test 2
Enter an integer: 100
Found at position 19

Test 3
Enter an integer: 55
Not found

Final answer

See example output

Detailed explanation

Background Concept

Good testing includes normal cases and edge cases. For searching, boundary values are particularly useful because they check whether the algorithm handles the ends of the array correctly. A "not found" case is also essential because it tests the failure path and confirms that the function eventually returns -1.

Understanding the Question

You must test the search three times using:

the smallest number in the array
the largest number in the array
a number not in the array

Because the program generates random values, the exact numbers will differ from run to run. So the outputs shown in the answer are an example based on the sample sorted list from part 2(d)(ii).

Approach

First look at the sorted array from your run. Identify its smallest and largest values. Then choose one integer that does not appear anywhere in that sorted list. Run the program three times and capture the output each time.

Step-by-Step Reasoning

In the sample sorted array:
0 3 6 8 14 19 21 27 34 39 45 50 57 61 64 72 76 88 93 100

The smallest value is 0, which is at index 0, so the expected result is Found at position 0.

The largest value is 100, which is at index 19, so the expected result is Found at position 19.

A value such as 55 is not present in the sample array, so the expected result is Not found.

If your own generated array is different, your test values and indexes will also be different. That is normal.

Key Takeaways

Use boundary values to test the first and last valid positions.
Always include a not-found test when testing a search algorithm.
For random-data programs, derive your test values from the actual run you are testing.

Common Mistakes

Choosing a "not found" value that is actually present in the array.
Using the smallest and largest numbers from the unsorted line without confirming them in the sorted array.
Giving the wrong index because of confusion between 0-based and 1-based positions.

Things to Be Careful About

The screenshots must match the actual array generated in that run. If the program is run again, a different random array may be produced, so the smallest value, largest value and missing value may all change. Check the sorted array carefully before choosing your three test inputs.

Techniques used

test the search with boundary values present in the arraytest the search with a value absent from the arraycheck the returned index matches the sorted array positions

Q3Medium-HardProgramming Paradigms (Procedural and Object-oriented)Algorithms and Abstract Data TypesFile Processing and Exception Handling

A program stores integers in ascending order in an ordered binary tree. The tree is implemented as a 2D array.

Each node is stored with three values:

a pointer to the left node
the data
a pointer to the right node.

All null values are stored as -1

The binary tree can store up to 50 nodes.

Nodes cannot be deleted from the binary tree.

Reference material

(a)

The binary tree is stored as a global array with the identifier TreeArray. The left pointer, the data and the right pointer of each node are initialised to -1

The global variable RootPointer stores the index of the root node in the tree, initialised to -1

The global variable FreeNode stores the index of the next free node in the array, initialised to 0

Write program code to declare and initialise TreeArray, RootPointer and FreeNode

Save your program as Question3_N25.

Copy and paste the program code into part 3(a) in the evidence document.

3M Similar

DifficultyMedium-Easy

Worked solution

Answer

TreeArray = [[-1 for Column in range(3)] for Row in range(50)]
RootPointer = -1
FreeNode = 0

Final answer

See program code

Detailed explanation

Background Concept

An array-based binary tree stores each node in a row of an array instead of using dynamic node objects with references. In this question, each row has three positions:

column 0: left pointer
column 1: data value
column 2: right pointer

A pointer does not store the child value directly. It stores the index of the child row in TreeArray. A null pointer is stored as -1, meaning “no child”.

Because the tree can hold up to 50 nodes, the array needs 50 rows. Since each node has exactly three fields, each row needs 3 columns.

RootPointer stores the index of the root node. If the tree is empty, there is no root yet, so RootPointer starts at -1.

FreeNode stores the next unused row in the array. At the very start, row 0 is the first free row, so FreeNode starts at 0.

Understanding the Question

You are asked only to declare and initialise the global data structures used by the rest of the program.

From the stem, you know:

the tree is stored in a global array called TreeArray
every left pointer, data item and right pointer must start as -1
RootPointer must start as -1
FreeNode must start as 0

So the required code is the initial setup, not the insertion logic.

Approach

The simplest Python representation is a 2D list with:

50 rows
3 columns per row
every entry initialised to -1

Then declare the two global variables with their starting values.

Step-by-Step Reasoning

TreeArray = [[-1 for Column in range(3)] for Row in range(50)]

range(50) creates 50 rows, indexed 0 to 49.
range(3) creates the three fields in each node.
every position is filled with -1, which matches the question requirement for null values and initial unused data.

RootPointer = -1

no values have been inserted yet
therefore the tree is empty
so there is no root node index yet

FreeNode = 0

the next available row is the first row in the array
so insertion should begin at index 0

This gives the exact starting state needed for later parts.

Key Takeaways

In an array-based tree, pointers are usually array indexes.
-1 is a common sentinel value for “null” or “no link”.
Initialisation matters because all later insertion logic depends on correct starting values.

Common Mistakes

Declaring a 1D array instead of a 2D array. Each node needs three separate fields.
Setting RootPointer to 0 immediately. The tree is empty at the start, so the root does not exist yet.
Forgetting to initialise every element to -1.
Using 49 rows instead of 50. The tree must store up to 50 nodes.

Things to Be Careful About

Keep the identifier names exactly as given: TreeArray, RootPointer, FreeNode.
Make sure the array indexes run from 0 to 49.
Do not confuse the data value field with a pointer field; all three positions are initialised to -1 before any insertions happen.

Techniques used

declare a 2D arrayinitialise every element with a sentinel valueset global pointer variables to their starting values

(b)

The procedure AddNode():

takes an integer to store in the binary tree as a parameter
stores the parameter in the next free node in the array
finds the position to store the data in the tree by following the appropriate pointers
updates the pointer of the new node's parent node.

The procedure outputs "The tree is full" if the parameter cannot be stored because the tree is full.

Write program code for AddNode()

Save your program.

Copy and paste the program code into part 3(b) in the evidence document.

7M Similar

DifficultyMedium-Hard

Worked solution

Answer

def AddNode(NewItem):
    global TreeArray, RootPointer, FreeNode

    if FreeNode == 50:
        print('The tree is full')
    else:
        TreeArray[FreeNode][0] = -1
        TreeArray[FreeNode][1] = NewItem
        TreeArray[FreeNode][2] = -1

        if RootPointer == -1:
            RootPointer = FreeNode
        else:
            Placed = False
            CurrentNode = RootPointer

            while not Placed:
                if NewItem < TreeArray[CurrentNode][1]:
                    if TreeArray[CurrentNode][0] == -1:
                        TreeArray[CurrentNode][0] = FreeNode
                        Placed = True
                    else:
                        CurrentNode = TreeArray[CurrentNode][0]
                else:
                    if TreeArray[CurrentNode][2] == -1:
                        TreeArray[CurrentNode][2] = FreeNode
                        Placed = True
                    else:
                        CurrentNode = TreeArray[CurrentNode][2]

        FreeNode += 1

Final answer

See program code

Detailed explanation

Background Concept

A binary search tree stores values so that:

smaller values go to the left subtree
greater values, and usually equal values if not otherwise specified, go to the right subtree

In an array-based implementation, each node is a row in TreeArray:

TreeArray[index][0] is the left pointer
TreeArray[index][1] is the data
TreeArray[index][2] is the right pointer

To insert a value:

make a new node in the next free row
if the tree is empty, make that row the root
otherwise start at the root and compare the new value with the current node
move left or right until a -1 pointer is found
change that -1 pointer to the index of the new row
increase FreeNode

Because nodes cannot be deleted, FreeNode can simply move upward from 0 to 49.

Understanding the Question

This part asks for the full AddNode() procedure. It must:

receive an integer parameter
store it in the next free row
find the correct location in the ordered tree
update the parent's left or right pointer
output The tree is full if no more rows are available

So this is not just “append to array”; it is proper BST insertion using array indexes as pointers.

Approach

The cleanest method is:

first test whether FreeNode shows the structure is full
if not full, write the new node into row FreeNode
if there is no root yet, set RootPointer to that row
otherwise loop down the tree from the root
- compare the new value with the current node's data
- if smaller, try the left pointer
- otherwise, try the right pointer
- if the chosen pointer is -1, store FreeNode there and stop
- otherwise follow that pointer and continue
when insertion is complete, increment FreeNode

Step-by-Step Reasoning

def AddNode(NewItem):

the procedure takes one integer argument, the value to insert

global TreeArray, RootPointer, FreeNode

these variables are global according to the question stem
without global, assignments inside the procedure would create local variables instead of updating the tree

if FreeNode == 50:

valid row indexes are 0 to 49
if FreeNode has reached 50, there is no free row left

print('The tree is full')

this matches the required output when insertion cannot happen

TreeArray[FreeNode][0] = -1
TreeArray[FreeNode][1] = NewItem
TreeArray[FreeNode][2] = -1

these three statements build the new node in the next free row
both child pointers start as null because the new node has no children yet

if RootPointer == -1:

this tests whether the tree is currently empty

RootPointer = FreeNode

the new node becomes the root of the whole tree

If the tree is not empty:

Placed = False

this flag controls the loop until the node has been linked into the tree

CurrentNode = RootPointer

start traversal at the root

while not Placed:

keep moving down until a free left or right pointer is found

if NewItem < TreeArray[CurrentNode][1]:

compare the new value with the current node's data
if smaller, it belongs in the left subtree

if TreeArray[CurrentNode][0] == -1:

there is no left child yet, so this is the insertion point

TreeArray[CurrentNode][0] = FreeNode

the current node's left pointer now points to the new row

Placed = True

insertion is finished

Otherwise:

CurrentNode = TreeArray[CurrentNode][0]

follow the left pointer and continue the search

The else branch handles values that are not smaller:

test the right pointer instead
if it is -1, link the new node there
otherwise follow the right pointer and continue

Finally:

FreeNode += 1

move on to the next unused row, ready for the next insertion

This order is important: the parent pointer must use the current value of FreeNode before it is incremented.

Key Takeaways

BST insertion is a repeated compare-and-follow-pointer process.
In an array-based tree, child links are indexes, not direct object references.
FreeNode is a simple but effective way to manage unused rows when deletion is not allowed.

Common Mistakes

Incrementing FreeNode too early, so the parent points to the wrong row.
Forgetting to set the new node's left and right pointers to -1.
Moving left and right the wrong way round after comparison.
Failing to stop the loop after insertion, causing an infinite loop or incorrect extra movement.
Missing the full-tree check.

Things to Be Careful About

The tree is full when there is no valid index left, so the check must match the 50-row limit exactly.
Use the data field TreeArray[CurrentNode][1] for comparison, not one of the pointer fields.
The question does not specify special duplicate handling, so sending non-smaller values to the right is a sensible consistent rule.
Update RootPointer only when the tree is empty.
Keep the exact procedure name AddNode and use the given global identifiers consistently.

Techniques used

check whether the array-based tree is fullstore a new node in the next free array rowtraverse the tree by following left and right pointerscompare the new value with current node dataupdate the parent pointer and advance the free-node index

(c)

The text file TreeData.txt stores 50 integers. Each integer is on a new line in the file.

The main program reads each integer from the file and stores each integer in the binary tree in the order they are read.

Write program code for the main program.

Save your program.

Copy and paste the program code into part 3(c) in the evidence document.

4M Similar

DifficultyMedium-Easy

Worked solution

Answer

with open('TreeData.txt', 'r') as FileHandle:
    for Line in FileHandle:
        Number = int(Line.strip())
        AddNode(Number)

Final answer

See program code

Detailed explanation

Background Concept

Sequential file processing means reading a text file one record after another in order. Here, each record is very simple: one integer per line.

A common Paper 4 pattern is:

open the file
loop through each line
strip the newline character
convert the text into the required data type
process it

Because the tree must store values in the order they are read, the main program should not sort or rearrange the data before calling AddNode().

Understanding the Question

The file TreeData.txt contains 50 integers, one on each line. The main program must:

read every value from the file
keep the same reading order
insert each value into the tree using AddNode()

So this part is about building the tree from the input file, not about writing the file back out.

Approach

Use a file-reading loop in Python:

open TreeData.txt for reading
iterate through each line in the file
remove the line ending with strip()
convert the remaining text to an integer using int()
pass that integer to AddNode()

This is short and directly matches the problem statement.

Step-by-Step Reasoning

with open('TreeData.txt', 'r') as FileHandle:

opens the text file in read mode
with closes the file automatically when finished

for Line in FileHandle:

reads each line one at a time from top to bottom
because there are 50 lines, the loop will run 50 times

Number = int(Line.strip())

strip() removes the newline character at the end of the line
int(...) converts the text such as '40' into the integer 40

AddNode(Number)

sends the integer to the insertion procedure
the order is preserved exactly as required by the question

That is all the main program needs for this part because the earlier parts have already provided the data structure and insertion procedure.

Key Takeaways

File data often arrives as strings and must be converted before use.
Sequential reading keeps the original file order.
Good main programs often do little more than read input and call well-named procedures.

Common Mistakes

Forgetting int(...), leaving the values as strings instead of integers.
Reading the whole file but not calling AddNode() for each line.
Using the wrong filename.
Adding extra sorting, which would change the required insertion order.

Things to Be Careful About

Keep the filename exactly as TreeData.txt.
Use .strip() so the newline character does not interfere with conversion.
Make sure AddNode() has already been defined before the main program runs.
The question says one integer per line, so one call to AddNode() should happen for each line read.

Techniques used

open a text file for readingread each line sequentiallyconvert string input to integercall a procedure for each value

(d)

The procedure WriteAllToFile() stores the content of TreeArray in a new text file with the filename Tree.txt. The file Tree.txt is not provided.

Each node in TreeArray is stored on one line with a comma separating each value.

For example, the current contents of TreeArray are:

Index	0	1	2
0	-1	20	1
1	-1	30	-1
...
49	-1	-1	-1

After writing TreeArray to the text file, Tree.txt will contain:

-1,20,1
-1,30,-1
...
-1,-1,-1

Write program code for WriteAllToFile()

Include exception handling when writing to the file.

Save your program.

Copy and paste the program code into part 3(d) in the evidence document.

5M Similar

DifficultyMedium

Worked solution

Answer

def WriteAllToFile():
    global TreeArray

    try:
        with open('Tree.txt', 'w') as FileHandle:
            for Index in range(50):
                FileHandle.write(f'{TreeArray[Index][0]},{TreeArray[Index][1]},{TreeArray[Index][2]}\n')
    except IOError:
        print('File could not be written')

Final answer

See program code

Detailed explanation

Background Concept

Writing to a text file means converting program data into lines of text. In this question, each row of the 2D tree array must become one line in the output file, with commas separating the three fields.

This is a simple CSV-style format:

left pointer
comma
data
comma
right pointer
newline

Exception handling is used to prevent the program from crashing if a run-time file error occurs, such as:

the file cannot be created
the location is not writable
the file is locked or inaccessible

In Python, this is done using try and except.

Understanding the Question

You must write the procedure WriteAllToFile() which:

writes all 50 rows of TreeArray
stores them in a new text file called Tree.txt
writes one node per line
separates the three values with commas
includes exception handling for file-writing errors

This means even unused rows near the end of the array still need to be written, usually as -1,-1,-1 if they are empty.

Approach

The plan is:

define the procedure
open Tree.txt for writing inside a try block
loop through indexes 0 to 49
build each line in the required left,data,right format
write a newline after each row
catch a file-writing error with except IOError

Step-by-Step Reasoning

def WriteAllToFile():

defines the required procedure name exactly as stated in the question

global TreeArray

the procedure needs to read the global array contents

try:

the file-writing code goes inside the protected block
if an I/O problem happens, control moves to except

with open('Tree.txt', 'w') as FileHandle:

opens a new text file named Tree.txt for writing
if the file already exists, write mode replaces its contents
with ensures the file is closed automatically

for Index in range(50):

every row from 0 to 49 must be written
the question wants the full contents of TreeArray, not only the used portion

FileHandle.write(f'{TreeArray[Index][0]},{TreeArray[Index][1]},{TreeArray[Index][2]}\n')

accesses the left pointer, data and right pointer in that order
places commas between them
adds a newline so each node appears on a separate line

except IOError:

catches a file input/output error

print('File could not be written')

gives a clear message rather than letting the program fail silently or crash

This produces exactly the format shown in the question example.

Key Takeaways

File output often needs explicit formatting, not just raw printing.
A 2D array row can be written field-by-field in a loop.
Exception handling is important for file operations because run-time errors are possible.

Common Mistakes

Writing only the used nodes instead of all 50 rows.
Forgetting commas between the three values.
Forgetting the newline, which would put all nodes on one line.
Omitting exception handling even though the question explicitly asks for it.
Using the wrong filename.

Things to Be Careful About

Keep the output order as left pointer, data, right pointer.
Use range(50) so every row is written.
The newline inside the string must be part of the code line; otherwise the file layout will be wrong.
Catching IOError is appropriate for this kind of file-writing problem.
Make sure the procedure name is exactly WriteAllToFile.

Techniques used

open a text file for writingformat array fields as comma-separated valuesiterate through all array rowshandle file-writing errors with a try-except block

(e)

(i)

Amend the main program to call WriteAllToFile()

Save your program.

Copy and paste the program code into part 3(e)(i) in the evidence document.

1M Similar

DifficultyEasy

Worked solution

Answer

WriteAllToFile()

Final answer

See program code

Detailed explanation

Background Concept

In a procedural program, the main program usually controls the overall sequence:

set up data structures
read input
process the data
produce output

A procedure call is used to trigger one self-contained task at the correct moment.

Understanding the Question

You are not being asked to rewrite the whole main program. You only need to amend it so that, after the tree has been built from the input file, the procedure WriteAllToFile() is called.

The important point is placement: the call should happen after all 50 values have been inserted, otherwise the output file would contain an incomplete tree.

Approach

Add one line:

call WriteAllToFile() once the reading and insertion loop has finished

That is enough to make the program create Tree.txt.

Step-by-Step Reasoning

WriteAllToFile()

calls the procedure from part (d)
this writes the current contents of TreeArray to Tree.txt
it should come after the loop that reads TreeData.txt and calls AddNode() for each value

If it were placed inside the file-reading loop, the file would be rewritten 50 times and would show intermediate states rather than the final finished tree.

Key Takeaways

A correct procedure call is not just about the name; timing and placement matter.
Output procedures are usually called after the data structure is fully built.

Common Mistakes

Placing the call inside the reading loop.
Misspelling the procedure name.
Forgetting the brackets when calling the procedure in Python.

Things to Be Careful About

Call WriteAllToFile() after all insertions are complete.
Use the exact capitalisation: WriteAllToFile().
Do not duplicate the call unless you actually want the file written multiple times.

Techniques used

call a procedure from the main programplace the call after data loading

(ii)

Test your program.

Take a screenshot that shows all of the content stored in the file Tree.txt

In this screenshot you need to make sure the filename is visible.

Save your program.

Copy and paste the screenshot(s) into part 3(e)(ii) in the evidence document.

1M Similar

DifficultyMedium-Easy

Worked solution

Answer

Using the 50 integers from TreeData.txt, the file Tree.txt will contain:

1,40,2
6,4,3
8,82,17
9,8,4
10,21,5
31,23,7
22,1,15
16,34,25
13,67,14
-1,6,-1
-1,9,11
-1,10,12
49,13,23
35,52,19
-1,68,28
-1,2,-1
48,28,26
18,89,20
-1,85,-1
21,66,-1
-1,91,33
-1,53,30
-1,0,-1
-1,15,24
32,19,-1
27,37,37
38,31,-1
-1,35,43
46,74,29
-1,76,45
-1,54,34
-1,22,-1
-1,16,47
-1,98,-1
44,61,-1
36,48,41
40,46,-1
-1,38,39
-1,30,-1
-1,39,-1
-1,41,-1
-1,49,42
-1,50,-1
-1,36,-1
-1,58,-1
-1,80,-1
-1,71,-1
-1,18,-1
-1,25,-1
-1,12,-1

Final answer

See expected file content

Detailed explanation

Background Concept

Testing a file-writing program means checking the external result, not just whether the program runs without errors. For this task, the final evidence is the content of Tree.txt.

Because the tree is represented as a 2D array, the output file is really a snapshot of that array after all insertions have been completed. Each line corresponds to one array row.

Understanding the Question

The exam asks for a screenshot of the produced file, with the filename visible. Since we are deriving the expected result here, the key thing is to work out exactly what Tree.txt must contain after:

reading all 50 integers from TreeData.txt
inserting them into the ordered binary tree in that exact order
writing every row of TreeArray to the file

So the answer is the final line-by-line content of the file.

Approach

To determine the file content:

insert each number into the BST using the AddNode() rules
remember that each inserted number occupies the next free array index
update left or right pointers of parent nodes as each insertion happens
once all 50 numbers are inserted, write row 0 to row 49 as left,data,right

The screenshot in the marking material confirms this final array state.

Step-by-Step Reasoning

The first few insertions show the pattern clearly:

40 goes into row 0 and becomes the root
4 is less than 40, so it becomes the left child of row 0, stored in row 1
82 is greater than 40, so it becomes the right child of row 0, stored in row 2
8 is greater than 4 but less than 40, so it becomes the right child of row 1, stored in row 3

This continues for all 50 values. Because insertion always uses the next free index, the row number is determined by input order, not by value order.

For example:

row 12 stores 13, and later row 49 stores 12
row 35 stores 48, row 36 stores 46, row 41 stores 49, and row 42 stores 50

Once all nodes have been inserted, WriteAllToFile() outputs each row exactly as it appears in the array. That produces the final file content shown in the answer.

A few sample lines interpreted:

1,40,2 means row 0 contains data 40, with left child at row 1 and right child at row 2
-1,6,-1 means row 9 contains data 6 and is a leaf node
36,48,41 means row 35 contains data 48, with left child at row 36 and right child at row 41

These lines are consistent with the final BST structure.

Key Takeaways

In an array-based BST, output files reflect row indexes as well as values.
Testing file output often means checking exact formatting and exact order.
The final content depends both on the insertion algorithm and on the input order.

Common Mistakes

Assuming the rows will appear in sorted order by data value. They will not; rows follow insertion order.
Forgetting that the file contains all array rows, not a traversal of the tree.
Swapping the order of the three fields when interpreting the file.
Leaving out negative one values for null pointers.

Things to Be Careful About

The file format is left pointer,data,right pointer, not data,left,right.
Each row must appear on its own line.
The screenshot requirement in the real exam is visual evidence, but the underlying correctness is the exact text content shown here.
If WriteAllToFile() were called too early, the file would be incomplete; it must be called after all 50 insertions.

Techniques used

run the completed programverify the generated file contentsmatch file rows to the final tree array state