GATE CS 2014 Set 3 Q.22 (CS Q.12): Binary Trees, Binary Search Trees and Balanced Trees

Consider the following rooted tree with the vertex labeled P as the root:

The order in which the nodes are visited during an in-order traversal of the tree is

SQPTRWUV

SQPTUWRV

SQPTWUVR

SQPTRUWV

Official answer and solution

Solution

Apply the multi-way tree in-order traversal definition: visit the first child's subtree, visit the node, then visit remaining children.

For a general rooted tree, the standard in-order traversal recursively performs:

Applying this traversal to the tree rooted at P:

Root P:
Children of P are Q (first child) and R (second child).
- Step 1: Traverse subtree at Q.
  - Q has one child S.
  - Traverse subtree at S: visit S.
  - Visit Q.
  - Sequence for Q's subtree: S Q.
- Step 2: Visit root P.
- Step 3: Traverse subtree at R.
  - Children of R are T, U, V.
  - Traverse first child T: visit T.
  - Visit node R.
  - Traverse second child U:
    - U has child W: visit W.
    - Visit U.
  - Traverse third child V: visit V.
  - Sequence for R's subtree: T R W U V.
Combine sequences:
$S \to Q \to P \to T \to R \to W \to U \to V$

This gives SQPTRWUV, which corresponds to option A.

Final answer

Common trap

Using binary tree in-order intuition on R's three children without properly placing R after its first child T.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.