GATE CS 2014 Set 3 Q12 — Trees

An in-order traversal of a binary tree recursively visits the nodes in the following order:

1. Traverse the left subtree.
2. Visit the root node.
3. Traverse the right subtree.

From the given tree structure, we can trace the traversal step-by-step:

• Left subtree of $P$ (rooted at $Q$):
  • Left child of $Q$ is $S$, and right child is $T$.
  • $\text{In-order}(Q) = S \to Q \to T$
• Root node: $P$
• Right subtree of $P$ (rooted at $R$):
  • $R$ has no left child, and its right child is $U$.
  • $U$ has left child $W$ and right child $V$.
  • $\text{In-order}(U) = W \to U \to V$
  • $\text{In-order}(R) = R \to \text{In-order}(U) = R \to W \to U \to V$

Combining these parts, the complete in-order traversal sequence is:

$$\text{S} \to \text{Q} \to \text{T} \to \text{P} \to \text{R} \to \text{W} \to \text{U} \to \text{V}$$