ITPEC FE Subject B April 2026 Question 9

Topic: Binary Search Tree

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

The function isPerfectBinaryTree checks whether the binary tree with a given root node is perfect. In a perfect binary tree, all the internal nodes have exactly two children, and all leaf nodes are at the same level. The function returns true if the tree is perfect, or false otherwise.
The class Node models a node of a binary tree as described in Table 1. A Node-type variable holds a reference to an instance of the class Node.

Table 1 Class Node

Member variableTypeDescription
KeyintegerInteger value stored in a node of a binary tree.
LeftNodeA reference to the left child of the node. If the left child does not exist, it is set to undefined.
RightNodeA reference to the right child of the node. If the right child does not exist, it is set to undefined.

Table 2 describes the functions used in the program.

Table 2 Functions

FunctionReturn valueDescription
pow(integer a,integer b)integerReturns the result of raising a to the power of b (i.e., ab ).
max(integer a,integer b)integerReturns the maximum of the two integers a and b.
[Program]
○ boolean: isPerfectBinaryTree(Node: root)
// The argument root holds a reference to the root node
// of a binary tree.
integer: height, size
height ← getHeight(root)
size ← getSize(root)
return A
○ integer: getHeight(Node: root)
integer: leftHeight, rightHeight
if (root is undefined)
return 0
endif
leftHeight ← getHeight(root.left)
rightHeight ← getHeight(root.right)
return 1 + max(leftHeight, rightHeight)
○ integer: getSize(Node: root)
if (root is undefined)
return 0
endif
return B

Answer Group

OptionAB

Explanation

A: size + 1 = pow(2, height), B: getSize(root.left) + getSize(root.right) + 1 — a perfect binary tree of height h holds exactly 2h − 1 nodes.

  • •B: the size of a subtree is the sizes of its two child subtrees plus the node itself, hence the + 1
  • •A: getHeight counts levels (an empty tree is 0, one node is 1). A perfect tree has 1 + 2 + 4 + … + 2h−1 = 2h − 1 nodes, and no other tree of that height has as many, so adding 1 to size must give pow(2, height)

Check the smallest trees:

  • •one node: height 1, size 1, and 1 + 1 = 21, so true
  • •root with two children: height 2, size 3, and 3 + 1 = 22, so true
  • •root with one child: height 2, size 2, and 2 + 1 ≠ 22, so false

Answer (b)

Why not others:

  • •(a), (d) and (g) — omit the + 1 in B, so every call adds only zeros and getSize always returns 0
  • •(c), (f) and (i) — subtract 1 in B, so a leaf counts as −1 and every size comes out too small
  • •(d), (e) and (f) — compare size with 2h−1, the number of leaves of a perfect tree rather than all its nodes; a root with two children has size 3, not 21 = 2
  • •(g), (h) and (i) — compare size with 2h, one more than a perfect tree's size, so they never return true for a non-empty tree

Key rule: Check a size or height formula on the smallest trees (one node, then two levels); they show at once whether a 1 must be added or subtracted, and on which side.

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.