ITPEC FE Subject B April 2024 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. Here, the array index starts at 1.

The procedure preorder traverses a binary tree and outputs the value of each node by following the sequence: root, left subtree, and right subtree using a stack (Last In, First Out). Each node of the binary tree is represented by the class Node. The table shows the description of the class Node. The Node-type variable holds a reference to an instance of the class Node. The argument root holds a reference to the root of the binary tree, which is an instance of the class Node. In the program, areas outside of the array must not be referenced.

Table Class Node

Member variableTypeDescription
infocharacterCharacter type value to be stored in a node of a binary tree.
leftNodeA reference to the left child of a binary tree. If there is no left child, the status is undefined
rightNodeA reference to the right child of a binary tree. If there is no right child, the status is undefined
[Program]
○ preorder(Node: root)
Node []: stack ← {undefined, ···, undefined}
// an array with sufficient number of elements
Node: v
integer: sp ← 1 // The stack pointer
stack[sp] ← root // Push root to the stack
while (sp is not A)
v ← stack[sp] // Pop an element from the stack
output v.info
sp ← sp - 1
if (B is not undefined)
sp ← sp + 1
stack[sp] ← B
endif
if (C is not undefined)
sp ← sp + 1
stack[sp] ← C
endif
endwhile

Answer group

OptionABC

Explanation

A: 0, B: v.right, C: v.left — the stack is empty when sp falls to 0, and the left child is pushed last so that it is popped first.

  • •sp indexes the top element and starts at 1 with the root. Each pop lowers it, so sp = 0 means the stack is empty: the loop runs while sp is not 0.
  • •Preorder visits the left subtree before the right one. A stack returns the last item pushed first, so the right child goes in first and the left child on top of it: B is v.right, C is v.left.

Trace for root R with children L and S, where L has children X and Y:

PoppedStack after the pushes (bottom to top)
RS, L
LS, Y, X
XS, Y
YS
Sempty, sp = 0

The output is R, L, X, Y, S: root, then the whole left subtree, then the right subtree.

Answer (b)

Why not others:

  • •(a) — pushing the left child first leaves the right child on top, so the right subtree is visited first: R, S, L, Y, X
  • •(c) and (d) — A -1 keeps the loop running once the stack is empty (sp = 0), so it reads stack[0], outside the array

Key rule: A stack reverses the order of what goes in, so push the children in the reverse of the order you want to visit them; with 1-based indexing an empty stack has a pointer of 0.

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.