ITPEC FE Subject B April 2025 Question 9

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.

Given the root of two binary trees, the aim of the following program is to check whether these two trees are identical. Two binary trees are defined as identical if they satisfy the following formal conditions:

  • •Structure: Both trees have the same structure, implying that for every corresponding node in the two trees, the arrangement of the left and right children is the same.
  • •Node Values: Each corresponding node in the two trees must contain the same value. Specifically, if tree T1 has a node N1 with value v1 and tree T2 has the corresponding node N2 with value v2, then v1 = v2.

The function isSameTree takes two instances of class TreeNode as the argument representing the root nodes of two binary trees, and returns true if the trees are identical, or false otherwise. The member variables of TreeNode are listed in the table below:

Table Explanation of the member variables of the class TreeNode

Member variableTypeDescription
valintegerThe integer value of a current node
leftTreeNodeLeft child node
rightTreeNodeRight child node
[Program]
○ boolean: isSameTree(TreeNode: p, TreeNode: q)
boolean: checkLeft, checkRight
if (p = undefined A q = undefined)
return true
endif
if (p = undefined B q = undefined)
return false
endif
if (p.val ≠ q.val)
return false
endif
checkLeft ← isSameTree(p.left, q.left)
checkRight ← isSameTree(p.right, q.right)
return checkLeft C checkRight

Answer group

OptionABC

Explanation

A: and, B: or, C: and — two missing nodes match, exactly one missing node does not, and otherwise both subtrees must match.

The function compares the two trees node by node, recursively:

  • •A: if both p and q are undefined, both subtrees are empty and therefore identical, so and returns true.
  • •B: this test is reached only when not both are undefined, so if either one is, one tree has a node the other lacks, and or returns false. It also keeps the program from reading p.val of an undefined node.
  • •C: with equal values at this node, the trees are identical only if the left subtrees and the right subtrees both are, so the results are joined with and.

Example: a single node 1 against a node 1 with left child 2. The values match; the left call gets undefined and a node, so B returns false, and C makes the whole result false.

Answer (c)

Why not others:

  • •(a) — A = or returns true whenever one node is missing, so the example above is judged identical; B = and is then dead code, since both-undefined has already returned.
  • •(b) — A and B are right, but C = or accepts trees whose right subtrees differ as long as the left ones match.
  • •(d) — the same A and B faults as (a), plus C = or.

Key rule: When comparing two recursive structures, handle both-empty, then one-empty, and join the children's results with and: one mismatch anywhere makes them different.

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.