ITPEC FE Subject B October 2025 Question 13

Topic: Binary Search Tree

From the answer group below, select the correct combination of answers to be inserted into A through C in the program.

Binary Search Trees (BST) are a fundamental data structure where each node has at most two children: a left child and a right child. The key property of a BST is that each value of all nodes in its left subtree are less than the value of the node, and each value of all nodes in its right subtree are greater than the value of the node. The table shows the member variables of the class Node. Node-type variable holds a reference to an instance of the class Node. Each node in a BST has a different value.

Table Member variables of class Node

Member variableTypeDescription
keyintegerInteger to be stored in the node.
leftNodeReference to the instance that holds the left child of a binary tree. If no left child exists, it is undefined.
rightNodeReference to the instance that holds the right child of a binary tree. If no right child exists, it is undefined.

The function remove removes a node with the same key value as the argument key from the BST specified by the argument node and returns the resulting BST. The function searches for a node with the same key value, and if the found node (call it X here) does not have a right subtree, the function returns its left subtree. If X has a right subtree, the function locates the node (call it Y here) with the smallest key value in the right subtree, replaces the key value of X with that of Y, and then removes Y. If there is no node with the same key value in the BST, the function performs no operations. The procedure test demonstrates this behavior by removing 1 node from a BST containing 7 nodes. The figure shows the BST before and after node removal.

12345671345673remove 2

Figure BST before and after node removal

[Program]
○ Node: remove(Node: node, integer: key)
Node: node2
if (node is undefined)
return undefined
elseif (key < node.key)
node.left ← remove(node.left, key)
elseif (key > node.key)
node.right ← remove(node.right, key)
elseif (node.right is undefined)
return node.left
else
node2 ← A
while (B)
node2 ← node2.left
endwhile
node.key ← node2.key
node.right ← remove(node.right, C)
endif
return node
○ test()
Node: root ← the root node of BST on the left side of the figure
root ← remove(root, 2)

Answer group

OptionABC

Explanation

A: node.right, B: node2.left is not undefined, C: node2.key — find Y as the leftmost node of X's right subtree, copy its key into X, then delete Y from that right subtree by its key.

The description fixes the method: Y is the node with the smallest key in X's right subtree. The smallest key of a BST is found by starting at its root and following left until there is no left child. So node2 starts at node.right (A) and moves left while node2.left is not undefined (B). After node.key ← node2.key, X holds Y's key, and Y must be removed from the right subtree by that key, remove(node.right, node2.key) (C).

Trace remove(root, 2) on the figure:

  • •At 5: 2 < 5, so recurse into the left subtree.
  • •At 2: the keys are equal and 2 has a right child (4), so take the else branch.
  • •node2 ← 4; 4 has a left child 3, so node2 ← 3; 3 has no left child, stop.
  • •Node 2's key becomes 3, then remove(4, 3): 3 < 4, recurse left; node 3 has no right subtree, so it returns its left subtree (undefined) and 4 loses its left child.

The result, 5 over 3 and 6, with 1 and 4 under 3 and 7 under 6, is the tree on the right of the figure.

Answer (h)

Why not others:

  • •(a), (b), (c) and (d) — node.left starts the search in X's left subtree, whose keys are all smaller than X's, so it can never reach the smallest key of the right subtree that the description asks for
  • •(e) and (f) — every key in X's right subtree is greater than key, so node2.key < key is false at once and node2 never leaves node.right. Here X would get key 4 instead of 3, and the old node 3 would stay in the right subtree of the new 4, breaking the BST order
  • •(g) — remove(node.right, key) searches the right subtree for the original key 2, which is not there, so nothing is removed and the tree ends up with two nodes holding 3

Key rule: To delete a node with two children, copy in the key of its in-order successor (the leftmost node of the right subtree), then delete the successor by that key; finding a minimum is a walk down left links, not a key comparison.

Binary Search Tree · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.