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

Key insight: in-order traversal visits the left subtree, then the node itself, then the right subtree (apply recursively).

• Traverse the left subtree of P (rooted at Q):

  • Q's left subtree is S, so visit S first.

  • Then visit Q.

• Visit the root P.

• Traverse the right subtree of P (rooted at R):

  • Visit R's left subtree: T (visit T).

  • Visit R.

  • Traverse R's right subtree (rooted at U):

    • Visit U's left subtree: W (visit W).

    • Visit U.

    • Visit U's right subtree: V (visit V).

Combine the visited nodes in order to get: S Q P T R W U V, which corresponds to the sequence SQPTRWUV.