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

IBDP Computer Science HL Paper 1 - All Chapters

Question

A list of strings should be inputted in the following order:
Freesia, Clarkia, Hibiscus, Gardenia, Bergenia, Erica
and inserted in a binary tree in such a way that an inorder traversal of the binary tree visits the nodes in alphabetical order.
(a) Sketch the resulting binary tree. $[3]$
(b) State the number of parent nodes in this binary tree. $[1]$

Most-appropriate topic code (CED):

• TOPIC B4.1: Fundamentals of ADTs — parts (a) and (b)
▶️ Answer/Explanation
Detailed solution

(a)
The strings are inserted one at a time. For a binary search tree, a string that comes alphabetically before a node is placed in its left subtree, while a string that comes alphabetically after it is placed in its right subtree.

(b)
A parent node is any node that has at least one child.

The parent nodes are:

• Freesia
• Clarkia
• Hibiscus

Therefore, the number of parent nodes is:

$\boxed{3}$

Answer: $3$ parent nodes.

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