IBDP Computer Science B4.1 Fundamentals of ADTs HL Paper 2 - New Syllabus

IBDP Computer Science HL Paper 2 - All Chapters

Question 

The extensive customer database of the car rental company is saved in a collection and needs to be read into an abstract data structure to ensure that searches can be done quickly.
(a) Outline why a linked list is slower to search than a binary tree.
The following class TNode has been defined to store Customer objects in a binary search tree.

public class TNode
{
    private TNode left;
    private Customer data;
    private TNode right;

    public TNode(Customer newCustomer)
    {
        left = null;
        data = newCustomer;
        right = null;
    }

    // getter and setter methods
}

Figure 12 shows a representation of the way customers are stored in the binary search tree. The nodes only show the customerID. However, each node stores a full Customer object.
Consider the following recursive algorithm.
public void print(TNode node)
{
    if (node != null)
    {
        print(node.left);
        output(node.data.getCustomerID());
        print(node.right);
    }
}
(b) State the output for the call print(root) given in Figure 12.
The output of the call print(root) is used to construct a new binary search tree.
(c) Sketch the resulting binary search tree using your output from part (b) as sequential input to create the new tree.
A new method is required to add the Customer objects from the binary tree to a sequential collection called myCollection. The order of the Customer objects in the collection must enable the tree to be restored in its original binary search tree form when the customers are read in a sequential order from myCollection.
(d) Construct the recursive code for a method storeBST() that will allow the binary tree of customers to be stored appropriately in myCollection. You may assume a method myCollection.add(Customer aCustomer) exists that appends aCustomer to the end of the sequential collection of customers.

Most-appropriate topic codes (IBDP Computer Science HL Paper 2):

• B2.2: Data structures – Parts (a), (b), (c), (d)
• B2.4: Programming algorithms – Parts (a), (b), (c), (d)
• B3.2: Fundamentals of OOP for multiple classes [HL only] – Part (d)
• B4.1: Fundamentals of ADTs [HL only] – Parts (a), (c), (d)

▶️ Answer/Explanation

(a)

For the correct answer:
A linked list is a sequential data structure, which in the worst case means that all elements have to be searched. A binary tree uses a binary search algorithm, where each comparison can eliminate approximately half of the remaining nodes. Therefore, a binary search tree can provide much faster searching when it is suitably balanced.

In a linked list, the search normally starts at the first node and examines nodes sequentially until the required item is found. In a binary search tree, the value being searched for can be compared with the current node and the search can continue only in the appropriate left or right subtree.

(b)

For the correct answer:
101, 337, 451, 519, 612, 788, 999

The method performs an inorder traversal. It first recursively visits the left subtree, outputs the current node, and then recursively visits the right subtree. For a binary search tree, this produces the customer IDs in ascending order.

(c)

For the correct answer:

The sequential input is already in ascending order. When these values are inserted into a standard binary search tree, each new value is greater than the previous values and therefore becomes the right child of the previous node. The resulting tree is completely unbalanced and resembles a linked list.

(d)

For the correct answer (5 marks):
Correct method signature; correct test for null; correct addition of the current data before recursive calls; correct recursive call to the left child; correct recursive call to the right child, all in a preorder sequence.

public void storeBST(TNode current)
{
    if (current != null)
    {
        myCollection.add(current.getData());
        storeBST(current.getLeft());
        storeBST(current.getRight());
    }
}

The method uses a preorder traversal: root, left subtree, right subtree. The current Customer object is added to myCollection before its children are processed. This ordering allows the original binary search tree structure to be reconstructed when the customers are subsequently inserted into an empty tree in the same sequence.

More IBDP Computer Science HL Paper 2 Questions..........
Scroll to Top