Computer Science 9618/42 — May/June 2024

Background Concept

This task uses three very common programming patterns:

1. A sentinel-controlled loop: the loop continues until a special value is entered. Here, that sentinel is no.
2. A linear search: each guess is compared with the answers one by one until a match is found or the list ends.
3. State update: when a correct answer is found, it is replaced so it cannot be counted again.

In Python, None is commonly used as a null-like value.

Understanding the Question

The procedure must:

• show the main word and total number of answers
• keep asking for words until the user types no
• say whether each word is a valid answer
• count how many valid answers were found
• replace any correct answer in WordArray with a null value

A key clue is that the main word is stored separately in the first array element, so the search must start from the next element, not from index 0.

Approach

Use this structure:

1. print WordArray[0] and NumberWords
2. set a Correct counter to 0
3. read a guess
4. while the guess is not no, search the answers from index 1 onward
5. if found, print success, increment the counter and replace that array element with None
6. if not found, print failure
7. read the next guess

A Boolean flag such as Found is useful so the program knows whether to print the "not an answer" message after the search.

Step-by-Step Reasoning

print("Main word:", WordArray[0]) outputs the main word. Because the file was loaded in order, the first element is always the main word.

print("Number of answers:", NumberWords) outputs how many valid answers exist.

Correct = 0 starts the correct-answer count.

Guess = input(...).lower() gets the first word from the user. Using lowercase helps comparisons because the file data is in lowercase.

while Guess != "no": creates the sentinel loop. As soon as the user enters no, the procedure stops asking for more words.

Found = False assumes the current guess is not present until the search proves otherwise.

for Index in range(1, NumberWords + 1): searches only the answer section of the array:

• index 0 = main word
• indices 1 to NumberWords = answers

If WordArray[Index] == Guess, then:

• the guess is a valid answer
• Correct increases by 1
• WordArray[Index] = None removes that answer from future use
• Found = True records success
• break stops the search early because the answer has already been found

If the loop finishes without a match, Found stays False, so the program prints that it is not an answer.

Finally, the program asks for the next guess and repeats.

Key Takeaways

• How to write a loop that ends on a sentinel value.
• How to search a list linearly.
• Why a flag variable helps after a search.
• How replacing found data prevents duplicate scoring.

Common Mistakes

• Searching from index 0 and accidentally treating the main word as an answer.
• Forgetting to reset Found to False for each new guess.
• Not using break, which can cause unnecessary searching or repeated handling.
• Forgetting to replace the correct answer, so the same word can be scored twice.

Things to Be Careful About

• range(1, NumberWords + 1) is correct because Python excludes the top value.
• Use None consistently as the null-like marker if you choose it.
• If you later compare against array contents, remember that replaced entries are no longer strings.
• The variable Correct is local here, which is fine unless another part needs it outside the procedure.

Background Concept

Once a program has been updating data during play, it can use that changed data to produce a summary. Here there are two summary tasks:

• calculate a percentage
• output the answers still left in the array

The percentage formula is:

Because correct answers were replaced with a null-like value, the unanswered ones are exactly the elements that are still not null.

Understanding the Question

This part does not replace Play() with a completely different idea. It says to amend it so that when the user stops:

• the percentage of answers entered is shown
• all answers not entered are shown

So the new code must happen after the sentinel value no ends the loop.

Approach

Keep the original Play() structure. Then, after the while loop finishes:

1. calculate and print the percentage using Correct and NumberWords
2. print a heading
3. loop through the answer elements again
4. print any element that is not None

Formatting the percentage to 2 decimal places makes the output neat and predictable.

Step-by-Step Reasoning

The loop body from part (c)(i) stays the same. It still searches for guesses, counts correct answers and replaces each correct answer with None.

When the user finally enters no, the condition Guess != "no" becomes false, so program control moves to the code after the loop.

Correct / NumberWords * 100 finds the percentage of valid answers entered.

Using:
print(f"Percentage correct: {Correct / NumberWords * 100:.2f}%")
means:

• divide to get the fraction correct
• multiply by 100 to convert to a percentage
• show exactly 2 decimal places

Then the program prints Answers not entered: as a heading.

The loop:
for Index in range(1, NumberWords + 1):
checks every stored answer.

If WordArray[Index] is not None, then that answer was never entered correctly, so it must be printed.

If the value is None, that answer was already found and should not be shown in the leftover list.

Key Takeaways

• How to add end-of-process summary code after a loop.
• How to calculate percentages from counts.
• How changed array contents can be reused to find what remains.

Common Mistakes

• Printing the percentage inside the loop instead of after the user stops.
• Using NumberWords - 1 in the percentage, which makes the total wrong.
• Printing None values because the code does not test before output.
• Forgetting that the main word is at index 0 and should not be listed as an unanswered answer.

Things to Be Careful About

• If you use None as the replacement value, test with is not None rather than comparing to a normal string.
• The percentage should use the original total number of answers, not the number still left in the array.
• Keep the output loop over indices 1 to NumberWords only.

Background Concept

Programs are often built from procedures that each do one job, then call the next procedure when their work is complete. This is procedural decomposition: one part loads the data, another part uses the data.

Understanding the Question

After ReadWords() has finished reading the file and counting the answers, the game should start automatically. That means ReadWords() must call Play() once the array and count are ready.

The important detail is the position of the call. Play() depends on WordArray and NumberWords, so it must not be called before those are fully set.

Approach

Keep the file-reading code the same. Add one extra line:

• call Play() after the file has been read and after NumberWords has been calculated

That is the only required amendment.

Step-by-Step Reasoning

The procedure still:

1. clears WordArray
2. opens the file
3. reads all lines into the array
4. sets NumberWords

Only then is Play() called.

If Play() were called earlier, it could try to output a main word or search answers before they existed. By placing the call at the end, the procedure guarantees the data is ready.

Key Takeaways

• A procedure call should happen only after all required data has been prepared.
• Order matters in procedural programs.

Common Mistakes

• Putting Play() inside the file-reading loop, which would start the game before the whole file is loaded.
• Calling Play() before NumberWords is calculated.
• Forgetting that the call must be inside ReadWords(), not just in the main program for this amendment.

Things to Be Careful About

• Keep Play() aligned with the rest of the code so it is outside the with block's loop body.
• The file should be fully read before gameplay begins.

Background Concept

A test run checks whether a complete program behaves correctly with specific inputs. For an interactive program, you trace:

• the chosen file
• the loaded data
• each user entry
• any updates to stored values
• the final summary output

Because correct answers are replaced with a null-like value, they will not appear later in the unanswered list.

Understanding the Question

The required test inputs are given in order:

1. easy
2. she
3. out
4. no

So the program must load Easy.txt, play one short game, then stop and show the summary.

From the reference file, the main word is house and there are 14 answers.

Approach

Trace the program exactly:

1. choose Easy.txt
2. load all words into WordArray
3. set NumberWords = 14
4. test she
5. test out
6. stop on no
7. calculate the percentage and print remaining answers

Step-by-Step Reasoning

The first input is easy, so the main program calls ReadWords("Easy.txt").

ReadWords() loads:

• WordArray[0] = house
• 14 answer words after that

So Play() begins by outputting:

• Main word: house
• Number of answers: 14

The next input is she.
That word appears in the file, so the program outputs she is an answer, increases Correct to 1 and replaces she in the array with None.

The next input is out.
That word does not appear in the stored answers, so the program outputs out is not an answer.

The next input is no, so the loop ends.

Now the percentage is calculated:

Finally, the program prints every answer still left in the array. Since she was removed, the remaining answers are all the original easy answers except she.

Key Takeaways

• How to dry-run an interactive file-based program.
• How previous updates to an array affect later output.
• How to derive percentage output from a test case.

Common Mistakes

• Counting 15 total words instead of 14 answers by accidentally including the main word.
• Forgetting that she is removed and should not appear in the leftover list.
• Treating out as valid even though it is not in the file.

Things to Be Careful About

• Different consoles may display prompts slightly differently, but the logical output must match the program.
• The percentage here is based on correct answers only, not all guesses entered.
• The unanswered list remains in the original file order.

Background Concept

When testing a larger data set, the same program logic still applies, but you must be more careful about counts and the exact order of remaining values. A dry run means following the state changes exactly as the program would.

Here, each correct answer is removed from the stored list. So after several correct guesses, the final unanswered list is simply the original list minus those removed items.

Understanding the Question

The required inputs are:

1. hard
2. fine
3. fined
4. idea
5. no

So the program loads Hard.txt, which has main word fainted and a large set of answer words. All three guesses before no must be checked against that stored answer list.

Approach

Trace the run in order:

1. load Hard.txt
2. count answers
3. check each guess with a linear search
4. replace each found word with None
5. stop on no
6. compute the percentage
7. print all answers not removed

Because the file is large, keeping the original order is important.

Step-by-Step Reasoning

The first input is hard, so ReadWords("Hard.txt") is called.

From the reference file:

• main word = fainted
• number of answers = 97

So Play() prints those two values first.

Next guess: fine

• fine is in the answer list
• output: fine is an answer
• Correct becomes 1
• the stored fine entry is replaced with None

Next guess: fined

• fined is also in the answer list
• output: fined is an answer
• Correct becomes 2
• the stored fined entry is replaced with None

Next guess: idea

• idea is in the answer list
• output: idea is an answer
• Correct becomes 3
• the stored idea entry is replaced with None

Next input: no

• loop ends

Now calculate the percentage:

Finally, output every remaining non-None answer in the original file order. Since fine, fined and idea were removed, they do not appear in the final list.

Key Takeaways

• Larger test runs still rely on the same basic tracing method.
• Accurate counting matters when calculating a percentage.
• Removing items during play changes the final summary output.

Common Mistakes

• Miscounting the hard file and using the wrong total instead of 97 answers.
• Forgetting to remove one of the correct answers from the final list.
• Changing the order of the leftover answers when printing them.

Things to Be Careful About

• fine and fined are different words; both must be found separately.
• The main word fainted is not part of the answers count.
• If you format the percentage to 2 decimal places in code, your expected output should use that same format consistently.

Background Concept

In this question, each tree node is represented as an object. In Object-Oriented Programming, a class is a blueprint and an object is one instance created from that blueprint. The Node class needs attributes to store the node's data and the links to its left and right children.

Because this tree is stored in a 1D array, the "pointers" are not memory addresses. They are integer indexes into the array. A pointer value of -1 is used to mean "no child". That is a common sentinel value in array-based linked structures.

A constructor is the special method that runs when an object is created. Its job is to put the object into a valid starting state.

Understanding the Question

You are asked only for the Node class declaration and its constructor. The table in the question tells you exactly what the class must contain:

• LeftPointer as an integer
• Data as an integer
• RightPointer as an integer
• a constructor that stores the parameter in Data
• both pointers initialised to -1

The question explicitly says not to declare the other methods here, so this part should contain only the class and constructor.

Approach

The simplest correct Python solution is:

1. Declare class Node:
2. Add Python comment lines to show the attributes, because the question asks Python candidates to include attribute declarations using comments.
3. Write __init__ with one parameter for the data value.
4. Set self.Data to that parameter.
5. Set self.LeftPointer and self.RightPointer to -1.

That fully matches the specification.

Step-by-Step Reasoning

class Node: starts the class definition.

The three comment lines are included because Python does not require separate attribute declarations, but Cambridge expects Python answers to show them as comments when asked.

def __init__(self, Data): is the Python constructor. self refers to the current object, and Data is the value passed in when the node is created.

self.Data = Data stores the constructor parameter in the object's data field.

self.LeftPointer = -1 and self.RightPointer = -1 mean the node starts with no left child and no right child.

That is exactly what a newly created node should look like before it is linked into the tree.

Key Takeaways

• A constructor initialises an object into a valid starting state.
• In an array-based tree, pointers are usually integer indexes.
• -1 is commonly used as a sentinel meaning "no link".
• Python attribute declarations can be shown with comments when required by the exam.

Common Mistakes

• Forgetting to set one or both pointers to -1.
• Setting Data to -1 instead of to the constructor parameter.
• Writing the other methods in this part even though the question says not to.
• Omitting the attribute comments for a Python answer.

Things to Be Careful About

• Use the exact attribute names from the question: LeftPointer, Data, RightPointer.
• The constructor parameter should become the node's data value immediately.
• Do not confuse a null pointer with 0; this question uses -1 for no child.
• Keep the answer limited to the constructor for this part.

Background Concept

Getter methods are accessor methods. They allow other parts of a program to read an object's data in a controlled way. In OOP, this supports encapsulation: the object manages access to its own attributes instead of exposing them carelessly.

A getter does not change anything. It simply returns the current value of one attribute.

Understanding the Question

This part tells you that GetLeft(), GetRight() and GetData() each return the relevant attribute. So the task is very direct: write three methods, each of which returns exactly one stored value from the Node object.

The important word is "relevant". Each method name tells you which attribute it must return.

Approach

For each method:

1. Use the exact method name given.
2. Give it only the self parameter in Python.
3. Return the matching attribute.

No parameters are needed because getters read from the current object only.

Step-by-Step Reasoning

def GetLeft(self): defines the first accessor.

return self.LeftPointer returns the left pointer stored in the current Node object.

def GetRight(self): defines the second accessor.

return self.RightPointer returns the right pointer.

def GetData(self): defines the third accessor.

return self.Data returns the integer data value.

These methods are intentionally short. That is normal for getters.

Key Takeaways

• A getter returns one attribute without modifying it.
• Method names must match the specification exactly in exam questions.
• Encapsulation often uses getters and setters even when the code seems simple.

Common Mistakes

• Returning the wrong attribute, such as GetLeft() returning self.RightPointer.
• Forgetting return.
• Adding unnecessary parameters to the getters.
• Using attribute names with the wrong capital letters.

Things to Be Careful About

• GetLeft() must return LeftPointer, not Data.
• GetRight() must return RightPointer.
• GetData() must return Data.
• In Python, use self. before each attribute name.

Background Concept

Setter methods are mutator methods. They change the state of an object by assigning a new value to one attribute. Together with getters, setters are a standard OOP technique used to control how attributes are updated.

A setter usually takes one parameter: the new value to store.

Understanding the Question

This part states that SetLeft(), SetRight() and SetData() each take a parameter and then store this in the relevant attribute. So you need three short methods, each doing a single assignment.

The key requirement is that the value passed in becomes the new value of the matching attribute.

Approach

For each setter:

1. Use the exact method name.
2. Include self and one extra parameter.
3. Assign that parameter to the correct attribute.

That is all that is required.

Step-by-Step Reasoning

def SetLeft(self, Value): creates a method that receives the new left pointer.

self.LeftPointer = Value stores that value in the node.

def SetRight(self, Value): receives the new right pointer.

self.RightPointer = Value stores it.

def SetData(self, Value): receives a replacement data value.

self.Data = Value stores it.

The parameter name can be any sensible identifier, but the destination attributes must match the specification exactly.

Key Takeaways

• A setter changes one attribute of an object.
• The setter parameter is the new value being written.
• Short methods can still be important because they support encapsulation.

Common Mistakes

• Assigning to the wrong attribute.
• Forgetting self. in Python.
• Returning a value from a setter even though none is needed.
• Changing more than one attribute inside a single setter.

Things to Be Careful About

• SetLeft() updates only LeftPointer.
• SetRight() updates only RightPointer.
• SetData() updates only Data.
• Keep the method names and attribute names exactly as given.

Background Concept

TreeClass is the class that manages the whole binary tree. Instead of using dynamically linked node references, this question stores the tree in an array. Each array element is a Node object, and the left and right pointers store array indexes.

Two extra attributes manage the structure:

• FirstNode stores the index of the root node
• NumberNodes stores how many nodes have been inserted so far

The constructor must also prepare the array so that positions 0 to 19 already contain Node objects.

Understanding the Question

You must declare TreeClass and write only its constructor. The specification tells you exactly what the constructor must do:

• set FirstNode to -1
• set NumberNodes to 0
• initialise each element of Tree[0:19] to a Node containing -1

That means the tree starts empty, but the storage space already exists.

Approach

The Python solution needs:

1. A class called TreeClass
2. Attribute comments for Python
3. A constructor __init__
4. Initial values for FirstNode and NumberNodes
5. A list called Tree
6. A loop that appends 20 separate Node(-1) objects

The loop is important because each position must hold its own Node object.

Step-by-Step Reasoning

class TreeClass: begins the class.

The comment lines document the required attributes.

Inside __init__, self.FirstNode = -1 means there is no root yet.

self.NumberNodes = 0 means no inserted nodes are in use.

self.Tree = [] creates the empty list.

The for loop runs 20 times, once for each valid index from 0 to 19.

self.Tree.append(Node(-1)) creates a new placeholder Node object whose data is -1 and whose left and right pointers are already -1 from the Node constructor.

At the end, the tree has storage ready for 20 nodes.

Key Takeaways

• A constructor may initialise both simple values and object collections.
• Array-based trees use indexes rather than memory references.
• Preparing the storage in advance is common in fixed-size exam questions.

Common Mistakes

• Forgetting to set FirstNode to -1.
• Forgetting to set NumberNodes to 0.
• Creating fewer than 20 elements.
• Using one Node object repeatedly instead of 20 separate objects.

Things to Be Careful About

• In Python, avoid using [Node(-1)] * 20 because that would repeat the same object reference 20 times.
• The indexes are 0 to 19, so the total size is 20.
• Keep the class name and attribute names exactly as given in the question.

Background Concept

A binary search tree stores values so that:

• smaller values go to the left subtree
• larger values, or equal values if that is the chosen rule, go to the right subtree

In this question, the tree is stored in an array, so each node's left and right links are array indexes. Insertion works by starting at the root and repeatedly comparing the new value with the current node's value:

• if smaller, follow the left pointer
• otherwise, follow the right pointer

When a -1 pointer is reached, that empty position is where the new node belongs. Then the parent's left or right pointer is updated to point to the new node's index.

Understanding the Question

You must write InsertNode(NewNode) for TreeClass. The question gives the algorithm in words:

• if the tree is empty, place the new node at index NumberNodes, increment NumberNodes, and set FirstNode to 0
• otherwise, store the new node at index NumberNodes, then search from FirstNode down the tree until the correct empty left or right link is found
• update the parent node's pointer
• increment NumberNodes

So this is both a tree traversal task and a pointer update task.

Approach

Use two cases.

Empty tree

If NumberNodes is 0, there are no inserted nodes yet. The new node goes at index 0, and that becomes the root.

Non-empty tree

1. Save the new node at index NumberNodes.
2. Start CurrentNode at FirstNode.
3. Keep a PreviousNode variable so you remember the parent.
4. Compare NewNode.GetData() with the current node's data.
5. Move left or right until CurrentNode becomes -1.
6. Use PreviousNode to update the correct pointer to NumberNodes.
7. Increment NumberNodes.

Step-by-Step Reasoning

if self.NumberNodes == 0: checks whether the tree is empty.

In the empty case, self.Tree[self.NumberNodes] = NewNode stores the node at index 0 because NumberNodes is 0.

self.NumberNodes += 1 records that one node is now in use.

self.FirstNode = 0 makes index 0 the root of the tree.

In the non-empty case, the new node is first stored in the next free array position: self.Tree[self.NumberNodes] = NewNode.

CurrentNode = self.FirstNode starts searching from the root.

The while CurrentNode != -1: loop continues while there is still a real node to inspect.

PreviousNode = CurrentNode remembers the parent before moving down a level.

If the new value is smaller than the current node's data, the search moves to the left child using GetLeft().

Otherwise, it moves to the right child using GetRight().

Eventually CurrentNode becomes -1. That means the search has gone past an existing child link and found where the new node should be attached.

The final if compares the new value with the parent node's data one more time. If smaller, the parent gets a left pointer to self.NumberNodes; otherwise, the parent gets a right pointer to self.NumberNodes.

Finally, self.NumberNodes += 1 moves the next free index forward.

Key Takeaways

• Binary search tree insertion is driven by repeated comparison.
• In an array-based tree, links are indexes, not object references.
• You often need both a current pointer and a previous pointer when inserting.
• Pointer updates happen only after the empty position has been found.

Common Mistakes

• Incrementing NumberNodes too early, which changes the index of the new node.
• Forgetting to keep track of the parent node.
• Updating CurrentNode before saving PreviousNode.
• Attaching the new node to the wrong side of the parent.
• Forgetting the empty-tree case.

Things to Be Careful About

• The question says to store NewNode in Tree at index NumberNodes first.
• FirstNode stores the root index, not the data value.
• -1 means "no child", so the search stops when a pointer becomes -1.
• The insertion rule here uses else for the right branch, so equal values would also go right.

Background Concept

An output routine for a data structure must know two things:

• when the structure is empty
• how much of the storage is actually in use

Here, Tree always has 20 elements, but not all 20 are valid inserted nodes. NumberNodes tells you how many positions from the start of the array are currently occupied by inserted nodes.

The question also states that the output must be in the order the nodes are saved in the array, not in sorted order and not by tree traversal order.

Understanding the Question

OutputTree() must print the left pointer, data value and right pointer for every inserted node. If there are no inserted nodes, it must print No nodes.

That means the method does not walk the tree from the root. It simply outputs array positions 0 up to NumberNodes - 1.

Approach

Use a simple two-part structure:

1. If NumberNodes is 0, print No nodes.
2. Otherwise, loop through the used section of the array and print three values from each Node object.

Using the getter methods keeps the method consistent with the OOP design already established.

Step-by-Step Reasoning

if self.NumberNodes == 0: checks whether any nodes have been inserted.

If true, print("No nodes") produces the required message and the procedure ends.

If false, the tree contains inserted nodes. The for Index in range(self.NumberNodes): loop runs from 0 up to the last used index.

On each iteration, the code outputs:

• GetLeft() for the left pointer
• GetData() for the stored integer
• GetRight() for the right pointer

This matches the exact order required by the question: left pointer, data, right pointer.

Because the loop only goes up to NumberNodes, unused placeholder nodes are not displayed.

Key Takeaways

• Use a counter like NumberNodes to process only valid data.
• Output order in a question may be array order rather than logical tree order.
• An empty-structure check is often a separate first case.

Common Mistakes

• Looping through all 20 array elements instead of just the inserted nodes.
• Printing Data before LeftPointer even though the required order is left, data, right.
• Traversing the tree recursively instead of printing in stored array order.
• Forgetting the No nodes case.

Things to Be Careful About

• range(self.NumberNodes) stops before self.NumberNodes, which is correct.
• Do not output unused Node(-1) placeholders.
• The required empty message is exactly No nodes.
• Keep the output order exactly as specified.

Background Concept

To use a class in a program, you create an instance of it. Instantiation calls the class constructor and returns a new object. That object can then store its own data and use its own methods.

In Python, this is done by writing the class name followed by parentheses.

Understanding the Question

The question is extremely specific: declare an instance of TreeClass with the identifier TheTree.

So there are only two important details:

• the class name must be TreeClass
• the variable name must be TheTree

Approach

Call the constructor for TreeClass and assign the resulting object to TheTree.

That single line both declares the identifier and creates the tree object.

Step-by-Step Reasoning

TreeClass() calls the constructor of the TreeClass class.

The constructor sets up:

• FirstNode
• NumberNodes
• the Tree array of 20 placeholder nodes

TheTree = ... stores that new object reference in the variable named TheTree.

Once this line has run, TheTree can be used to call methods such as InsertNode() and OutputTree().

Key Takeaways

• Instantiating a class creates an object ready for use.
• The identifier name matters in exam questions when it is specified.
• Constructors run automatically when the object is created.

Common Mistakes

• Using the wrong identifier, such as tree instead of TheTree.
• Forgetting the parentheses after TreeClass.
• Writing only the class name without creating an instance.

Things to Be Careful About

• Match the capital letters exactly: TheTree and TreeClass.
• This line belongs in the main program, not inside a class definition.

Background Concept

The main program is the part that creates objects and coordinates method calls. In OOP, you often:

1. create an instance of a class
2. create any needed data objects
3. call methods in the required order

For a binary search tree, insertion order matters because it determines the final shape of the tree. Even with the same set of values, a different insertion order can produce a different structure.

Understanding the Question

You must amend the main program so that it:

• uses the existing TheTree object
• inserts the integers 10, 11, 5, 1, 20, 7, 15 in exactly that order
• then calls OutputTree()

The important detail is that InsertNode() takes a Node object, not a raw integer. So each value must be wrapped in Node(...) first.

Approach

Start with the object created in part (c)(i):

TheTree = TreeClass()

Then call InsertNode() once for each value, using Node(value) as the parameter. Finally call TheTree.OutputTree().

The method calls must stay in the order given by the question.

Step-by-Step Reasoning

TheTree = TreeClass() creates the tree object.

TheTree.InsertNode(Node(10)) creates a Node containing 10 and inserts it. This becomes the root.

TheTree.InsertNode(Node(11)) inserts 11, which goes to the right of 10.

TheTree.InsertNode(Node(5)) inserts 5, which goes to the left of 10.

TheTree.InsertNode(Node(1)) inserts 1, which goes left of 10, then left of 5.

TheTree.InsertNode(Node(20)) inserts 20, which goes right of 10, then right of 11.

TheTree.InsertNode(Node(7)) inserts 7, which goes left of 10, then right of 5.

TheTree.InsertNode(Node(15)) inserts 15, which goes right of 10, right of 11, then left of 20.

Finally, TheTree.OutputTree() prints the stored nodes in array order.

Key Takeaways

• Main programs often construct objects and then call methods on them.
• If a method expects an object parameter, pass an object, not just a primitive value.
• Insertion order matters for trees.

Common Mistakes

• Calling InsertNode(10) instead of InsertNode(Node(10)).
• Changing the order of insertions.
• Forgetting the final OutputTree() call.
• Recreating TheTree midway through the program.

Things to Be Careful About

• The question asks for the integers in the order given; do not sort them first.
• Keep the identifier as TheTree.
• Each insertion needs a new Node object.
• The output is produced only after all seven insertions.

Background Concept

When values are inserted into a binary search tree, each new value is placed by comparing it with existing nodes and moving left for smaller values or right for larger values. In this question, the tree is stored in an array, so the output does not show a diagram of the tree directly. Instead, it shows for each stored node:

• the index of the left child
• the data value
• the index of the right child

Because OutputTree() prints nodes in array order, the output rows correspond to the order of insertion, not to an in-order traversal.

Understanding the Question

The exam task says to test the program and capture the output. Since the inserted values are fixed, there is one expected result. You need the final three-column output after inserting:

10, 11, 5, 1, 20, 7, 15

The important point is that the printed rows show the internal array-based representation of the tree.

Approach

Work through the insertions one at a time, keeping track of the array index used for each new node:

• index 0 gets 10
• index 1 gets 11
• index 2 gets 5
• index 3 gets 1
• index 4 gets 20
• index 5 gets 7
• index 6 gets 15

Then update the left or right pointer of the correct parent each time.

Step-by-Step Reasoning

Insert 10 at index 0. It is the first node, so FirstNode = 0.

Insert 11 at index 1. Since 11 > 10, it becomes the right child of index 0. So node 0 gets right pointer 1.

Insert 5 at index 2. Since 5 < 10, it becomes the left child of index 0. So node 0 gets left pointer 2.

Insert 1 at index 3. Compare with 10 then 5: it goes left of 5. So node 2 gets left pointer 3.

Insert 20 at index 4. Compare with 10 then 11: it goes right of 11. So node 1 gets right pointer 4.

Insert 7 at index 5. Compare with 10 then 5: it goes right of 5. So node 2 gets right pointer 5.

Insert 15 at index 6. Compare with 10, then 11, then 20: it goes left of 20. So node 4 gets left pointer 6.

Now print each used array entry in order:

• index 0: left 2, data 10, right 1
• index 1: left -1, data 11, right 4
• index 2: left 3, data 5, right 5
• index 3: left -1, data 1, right -1
• index 4: left 6, data 20, right -1
• index 5: left -1, data 7, right -1
• index 6: left -1, data 15, right -1

That gives the required console output.

Key Takeaways

• You can represent a tree using array indexes instead of direct links.
• Tree insertion order affects the final internal structure.
• Output order here is insertion/storage order, not sorted order.

Common Mistakes

• Assuming the output should be numerically sorted.
• Forgetting that 15 becomes the left child of 20.
• Printing all 20 array elements instead of only the 7 inserted nodes.
• Mixing up child indexes with the data values.

Things to Be Careful About

• -1 means no child exists.
• The first column is LeftPointer, the second is Data, and the third is RightPointer.
• The row order is index order from 0 to NumberNodes - 1.
• A screenshot in the real exam can show spacing differences, but the values themselves must match exactly.

Background Concept

Recursive insertion sort works by solving a smaller version of the same problem first. The base case is when the list has one element or fewer, because that is already sorted. The recursive step sorts the first n - 1 elements, then inserts the last element into its correct position within that sorted section.

A recursive routine must always have:

• a base case, so it stops calling itself
• a recursive call on a smaller problem
• logic after the recursive call to combine the result

Here, the combination step is the insertion process.

Understanding the Question

The question gives you pseudocode for RecursiveInsertion() and asks you to write the equivalent program code. So this is mainly a translation task. You are not inventing a new algorithm; you are converting the given logic into Python while keeping the same behaviour.

The function must:

• take an integer array and a count of how many elements to consider
• recursively sort the array into ascending order
• return the sorted array

Approach

Follow the pseudocode structure closely:

1. If there is only 1 element or fewer, return immediately.
2. Otherwise, recursively sort the first NumberElements - 1 items.
3. Store the last item from the current section in LastItem.
4. Move left through the sorted section using CheckItem.
5. While elements are greater than or equal to LastItem, shift them one place right.
6. Put LastItem into the gap that is left.
7. Return the array.

In Python, the list is mutable, so the recursive call changes the same list in place.

Step-by-Step Reasoning

The function header is:

def RecursiveInsertion(IntegerArray, NumberElements):

This matches the two parameters from the pseudocode.

The base case is:

if NumberElements <= 1:
    return IntegerArray

If there is only one element, no sorting is needed.

Otherwise, the function sorts the earlier part first:

RecursiveInsertion(IntegerArray, NumberElements - 1)

That means when the function returns from this call, the first NumberElements - 1 items are already sorted.

Now the current last item is saved:

LastItem = IntegerArray[NumberElements - 1]
CheckItem = NumberElements - 2

LastItem is the element to insert. CheckItem starts at the element just before it.

The pseudocode uses a Boolean called LoopAgain to decide whether shifting should continue. The first test checks whether CheckItem has gone before the start of the array. If not, it checks whether the current value is smaller than LastItem. If it is smaller, insertion should stop.

While LoopAgain is true, the larger item is shifted right:

IntegerArray[CheckItem + 1] = IntegerArray[CheckItem]
CheckItem = CheckItem - 1

Then the same stopping test is repeated.

When the loop ends, the correct insertion position is CheckItem + 1, so:

IntegerArray[CheckItem + 1] = LastItem

Finally, return the array.

This produces ascending order because values larger than LastItem are moved right until the correct position is found.

Key Takeaways

• Recursive insertion sort sorts a smaller prefix first, then inserts one item.
• The base case prevents infinite recursion.
• Careful index handling is essential: NumberElements - 1 is the last item in the current section.
• Python lists can be modified in place and still returned.

Common Mistakes

• Using IntegerArray[NumberElements] instead of IntegerArray[NumberElements - 1], which causes an index error.
• Forgetting the base case, which would cause infinite recursion.
• Returning nothing, even though the function is supposed to return the array.
• Moving CheckItem the wrong way, for example increasing instead of decreasing it.

Things to Be Careful About

• Python uses zero-based indexing, so the last valid position is one less than the number of elements.
• The loop must stop if CheckItem < 0 before trying to read IntegerArray[CheckItem].
• Keep the function name exactly RecursiveInsertion so later calls work correctly.
• The question wants ascending order, so the insertion logic must place smaller values earlier in the array.

Background Concept

After a function is written, the main program must call it with the correct parameters and then use the returned result. In Python, len(...) gives the number of elements in a list. Also, because lists are mutable, a sort function may change the original list. Using .copy() creates a separate list so the original values are still available later.

Understanding the Question

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

• calls RecursiveInsertion()
• passes in NumberArray and the number of elements
• outputs the word Recursive
• outputs the returned sorted array

The earlier part already created NumberArray, and part (b)(i) already created the function.

Approach

Make one function call and store its returned value. Then print the label and the sorted result. Using NumberArray.copy() is a good choice because later parts still need the original unsorted list.

Step-by-Step Reasoning

The function needs two parameters:

1. the array itself
2. the number of elements

In Python, the number of elements is found using:

len(NumberArray)

The call is:

SortedRecursive = RecursiveInsertion(NumberArray.copy(), len(NumberArray))

This does three things:

• makes a copy of the original list
• sorts that copied list recursively
• stores the returned sorted list in SortedRecursive

Then the label is printed exactly as required:

print("Recursive")

Finally, the returned array is displayed:

print(SortedRecursive)

That shows the sorted contents in Python list format.

Key Takeaways

• Always pass the right number and type of parameters to a function.
• len(...) is the normal way to get a list size in Python.
• .copy() is useful when you want to keep the original list unchanged.
• Store returned data in a variable before using or printing it.

Common Mistakes

• Passing only the array and forgetting the number of elements.
• Printing NumberArray instead of the returned sorted array.
• Omitting the word Recursive.
• Sorting the original array directly and then not having the unsorted version available for later tasks.

Things to Be Careful About

• Keep the output word exactly Recursive with a capital R.
• Use len(NumberArray), not a hard-coded number unless you are certain the size will never change.
• If you do not use .copy(), later parts may work on an already sorted list instead of the original initialised one.

Background Concept

Testing a sort means checking that the output is in the required order and that all original values are still present. For an ascending insertion sort, the smallest value should appear first and the largest last.

Understanding the Question

This part asks for the output screenshot after testing the program from part (b). At this stage, the main program prints the word Recursive and then prints the sorted array returned by RecursiveInsertion().

Approach

Take the original values and arrange them from smallest to largest:

1, 8, 15, 22, 85, 100, 644

Then place that under the label that the program prints.

Step-by-Step Reasoning

The original array is:

100, 85, 644, 22, 15, 8, 1

Sorting into ascending order gives:

• smallest: 1
• then 8
• then 15
• then 22
• then 85
• then 100
• largest: 644

So the sorted array is:

[1, 8, 15, 22, 85, 100, 644]

Because part (b)(ii) prints the label first, the full console output is:

Recursive
[1, 8, 15, 22, 85, 100, 644]

Key Takeaways

• A successful sort keeps the same values but changes their order correctly.
• Testing output should reflect exactly what the program prints.
• For Python, printing a list shows square brackets and commas.

Common Mistakes

• Forgetting the label Recursive in the screenshot.
• Writing the numbers in descending order instead of ascending order.
• Missing a value or duplicating one during the manual check.

Things to Be Careful About

• The screenshot should match your own program's formatting.
• If you printed items one per line instead of as a list, your screenshot would differ, but it still must show the correct sorted sequence.
• Make sure 644 remains in the output; sorting should not remove any data.

Background Concept

Iterative insertion sort builds a sorted section from left to right. At each pass, one value is taken from the unsorted part and inserted into the correct place in the sorted part. Unlike the recursive version, the iterative version uses a loop to repeat this process for each position.

Understanding the Question

You must write IterativeInsertion() so that it performs the same sorting job as RecursiveInsertion(), but without recursion. The result still needs to be an ascending sort of the integer array.

Approach

Use the standard insertion sort pattern:

1. Start from the second element.
2. Treat the earlier part as already sorted.
3. Store the current element in a temporary variable.
4. Move left while earlier items are larger.
5. Shift those larger items right.
6. Insert the stored value into the gap.
7. Repeat until the list is fully sorted.

Step-by-Step Reasoning

The function header is:

def IterativeInsertion(IntegerArray):

Only the array is needed because the function can find its own length using len(IntegerArray).

The outer loop is:

for Pointer in range(1, len(IntegerArray)):

This starts at index 1, because a single first element at index 0 is already sorted by itself.

For each pass:

LastItem = IntegerArray[Pointer]
CheckItem = Pointer - 1

LastItem is the value to insert. CheckItem begins at the item immediately to its left.

The inner loop is:

while CheckItem >= 0 and IntegerArray[CheckItem] > LastItem:

This means:

• stay within the array
• keep shifting while earlier values are too large

Inside that loop:

IntegerArray[CheckItem + 1] = IntegerArray[CheckItem]
CheckItem = CheckItem - 1

This creates room for LastItem.

Once the correct position is found, insert the saved value:

IntegerArray[CheckItem + 1] = LastItem

Finally, after all passes, return the array.

This produces the same final result as the recursive version, but the repetition is controlled by a for loop rather than repeated function calls.

Key Takeaways

• Iteration can replace recursion when the repeated pattern is easy to express as a loop.
• In insertion sort, the left side of the list grows into a sorted section.
• The temporary variable is essential so the current value is not lost during shifting.

Common Mistakes

• Starting the outer loop at index 0 instead of 1.
• Using the wrong comparison in the while condition, which can sort in the wrong order.
• Forgetting to insert LastItem after shifting finishes.
• Returning nothing from the function.

Things to Be Careful About

• Python is zero-indexed, so range(1, len(IntegerArray)) is the correct set of passes.
• The condition must check CheckItem >= 0 before reading IntegerArray[CheckItem].
• Use > for ascending order, because only larger earlier values need to shift right.

Background Concept

When two different sorting functions must be tested on the same starting data, it is good practice to preserve the original list. Otherwise, the second sort may simply receive an already sorted list, which is not what the question intends by saying the original initialised array.

Understanding the Question

This part extends the main program again. It must now also:

• call IterativeInsertion()
• use the original initialised NumberArray
• output the word iterative
• output the returned array

The word also means the earlier recursive output should still remain in the program.

Approach

Make a second function call, again using a copy of the original list. Store the returned list in a new variable, then print the required label and list.

Step-by-Step Reasoning

The call is:

SortedIterative = IterativeInsertion(NumberArray.copy())

This sends a fresh copy of the original unsorted values into the iterative insertion sort.

Then print the exact required label:

print("iterative")

Finally, print the result:

print(SortedIterative)

Because the list is sorted into ascending order, this will show the same sequence as the recursive version.

Key Takeaways

• Reuse of the same original data is important when comparing algorithms.
• Separate variables such as SortedRecursive and SortedIterative make the program easier to follow.
• Output labels help distinguish which algorithm produced which result.

Common Mistakes

• Calling IterativeInsertion() on SortedRecursive instead of the original data.
• Printing IterativeInsertion without parentheses, which prints the function object rather than calling it.
• Using the wrong label case, for example Iterative instead of iterative.

Things to Be Careful About

• The question says also, so this code is added to the existing main program rather than replacing the recursive section.
• Keep the output word exactly iterative in lower case.
• Passing NumberArray.copy() avoids changing the original list.

Background Concept

If two algorithms are intended to perform the same sort, a simple test is to run both on the same input and compare their outputs. If both produce the same correctly sorted sequence, that is strong evidence that both implementations are working.

Understanding the Question

At this stage, the main program now includes both the recursive sort output and the iterative sort output. The screenshot should therefore show both sections of output, not just the new one.

Approach

Work out the sorted order once, then show it twice: once after the Recursive label and once after the iterative label.

Step-by-Step Reasoning

The original values are:

100, 85, 644, 22, 15, 8, 1

Sorted in ascending order, they become:

[1, 8, 15, 22, 85, 100, 644]

Both sorting methods should produce exactly that same list.

So the full output at this point is:

Recursive
[1, 8, 15, 22, 85, 100, 644]
iterative
[1, 8, 15, 22, 85, 100, 644]

Key Takeaways

• Different implementations of the same algorithm should give the same final sorted data.
• Testing with identical input is important when comparing results.
• Console output must include everything printed by the current version of the program.

Common Mistakes

• Showing only the iterative section and forgetting the earlier recursive output.
• Printing different orders because one function was run on already changed data.
• Misspelling or changing the case of iterative.

Things to Be Careful About

• Use the original data for both sorts, not the output of one sort as the input to the other.
• If your program prints list formatting with brackets and commas, your screenshot should reflect that exactly.
• The two sorted lines should be identical in content.

Background Concept

Binary search is an efficient searching algorithm for sorted data. It works by repeatedly checking the middle element of the current search range:

• if the middle value matches, the search is finished
• if the target is smaller, search the left half
• if the target is larger, search the right half

A recursive binary search expresses this by calling itself on a smaller half each time. The stopping condition is when the search range becomes empty.

Understanding the Question

You need to write a recursive function called BinarySearch() that takes:

• the sorted integer array
• First, the first index in the current search range
• Last, the last index in the current search range
• ToFind, the value being searched for

It must return the index where the value is found, or -1 if the value is not present.

Approach

Use the standard recursive binary search structure:

1. If First > Last, the range is empty, so return -1.
2. Find the middle index using integer division.
3. Compare the middle element with ToFind.
4. Return the middle index if it matches.
5. Otherwise, recurse into the appropriate half.

Step-by-Step Reasoning

The function header is:

def BinarySearch(IntegerArray, First, Last, ToFind):

The empty-range base case is:

if First > Last:
    return -1

This is essential. Without it, the function would keep calling itself even when there is nowhere left to search.

The middle position is calculated as:

Middle = (First + Last) // 2

// is integer division in Python, which is what is needed for an index.

Next compare the middle value with the target:

if IntegerArray[Middle] == ToFind:
    return Middle

If the target is smaller than the middle value, the correct half is the left side:

elif ToFind < IntegerArray[Middle]:
    return BinarySearch(IntegerArray, First, Middle - 1, ToFind)

If not, the target must be larger, so search the right side:

else:
    return BinarySearch(IntegerArray, Middle + 1, Last, ToFind)

Each recursive call reduces the search range, so the search eventually finds the value or reaches the base case.

Key Takeaways

• Binary search only works correctly on sorted data.
• The recursive search range must shrink each time.
• -1 is a common sentinel value meaning "not found".
• Integer division is needed to produce a valid middle index.

Common Mistakes

• Trying to use binary search on the original unsorted array.
• Forgetting the base case First > Last.
• Using len(array) as the last index instead of len(array) - 1 when calling the function.
• Recursing with Middle instead of Middle - 1 or Middle + 1, which can cause an infinite loop.

Things to Be Careful About

• Python lists are zero-indexed.
• The function must return the recursive call result; otherwise the found index is lost.
• The search value and the array elements are integers, so comparisons are numeric, not string-based.

Background Concept

A search function often returns a sentinel value to indicate failure. Here, -1 means the item was not found. The main program must therefore examine the returned value and decide what to print.

Understanding the Question

You must amend the main program so that it:

• calls BinarySearch() with the sorted array
• searches for 644
• prints Not found if the result is -1
• otherwise prints the index returned by the function

The phrase "the sorted array" means you should use the already sorted version, not the original unsorted NumberArray.

Approach

Call the function using the correct first and last index values for the whole list. Store the returned value in a variable. Then use an if statement to choose between the message and the index.

Step-by-Step Reasoning

For a Python list of length n, the first valid index is 0 and the last valid index is n - 1.

So the correct call is:

FoundIndex = BinarySearch(SortedRecursive, 0, len(SortedRecursive) - 1, 644)

This searches the whole sorted list for the integer 644.

Next, test for the sentinel value:

if FoundIndex == -1:
    print("Not found")
else:
    print(FoundIndex)

If the item does not exist, the function returns -1, so the program prints Not found.

If the item does exist, the returned index is printed.

Key Takeaways

• A sentinel like -1 is a standard way to indicate failure in a search.
• Binary search must be called with correct boundary indices.
• The main program, not the function, decides how to present the result to the user.

Common Mistakes

• Calling the search on NumberArray before sorting it.
• Using len(SortedRecursive) as the last index instead of len(SortedRecursive) - 1.
• Printing FoundIndex without first checking whether it is -1.

Things to Be Careful About

• The question asks to output Not found exactly if the value is missing.
• In Python, 0 is a valid index, so you must not treat 0 as meaning not found.
• Use the sorted array variable, such as SortedRecursive, not the original unsorted list.

Background Concept

A full program test checks that all parts work together: data setup, sorting, second sorting method, and searching. When a binary search finds a value in a Python list, it returns the zero-based index of that value.

Understanding the Question

This final screenshot is for the fully amended program. That means the console output now includes:

• the recursive sort result
• the iterative sort result
• the output from the binary search for 644

Because 644 is present in the sorted array, the program should print its index rather than Not found.

Approach

Use the sorted array already obtained:

[1, 8, 15, 22, 85, 100, 644]

Then determine the position of 644 using Python's zero-based indexing.

Step-by-Step Reasoning

After sorting, both methods give:

[1, 8, 15, 22, 85, 100, 644]

Now number the indices:

• index 0 -> 1
• index 1 -> 8
• index 2 -> 15
• index 3 -> 22
• index 4 -> 85
• index 5 -> 100
• index 6 -> 644

So 644 is found at index 6.

The complete output is therefore:

Recursive
[1, 8, 15, 22, 85, 100, 644]
iterative
[1, 8, 15, 22, 85, 100, 644]
6

Key Takeaways

• Final testing should reflect the whole current state of the program, not just the newest part.
• Binary search returns an index, not the value itself.
• Python uses zero-based indexing, so the seventh item is at index 6.

Common Mistakes

• Writing 7 because of counting positions from 1 instead of indices from 0.
• Showing Not found even though 644 is clearly in the array.
• Omitting the earlier recursive and iterative outputs from the screenshot.

Things to Be Careful About

• The screenshot should match your exact print statements.
• If you changed the output format in your own code, your display may look slightly different, but it must still clearly show both sorted arrays and the found index.
• For Python, the index of 644 in this sorted list is 6, not 7.