We can test whether a node ‘ m’ is a proper ancestor of a node ‘ n’ by testing whether ‘ m’ precedes ‘ n’ in X-order but follows ‘ n’ in Y-order , where X and Y are chosen from {pre, post, in}. Determine all those pairs X and Y for which this statement holds.

[Answer of Question 2] This question is about tree traversals and how ancestor–descendant relationships are reflected in traversal orders.

We are given:

• A node m is a proper ancestor of node n
• Test condition:
  m precedes n in X-order
  m follows n in Y-order
• Where X, Y ∈ {preorder, postorder, inorder}

We must find all valid (X, Y) pairs for which this condition is always true.

Key traversal properties (very important)

1. Preorder (Pre)

• Visit root before children
• Ancestor always appears before descendant

2. Postorder (Post)

• Visit root after children
• Ancestor always appears after descendant

3. Inorder (In)

• Root appears between left and right subtrees
• No consistent ordering between ancestor and descendant in general

Analyze all possible (X, Y) combinations

We want:

• m precedes n in X
• m follows n in Y

Case 1: X = Preorder

• Ancestor always precedes descendant ✅

Now Y must be a traversal where ancestor follows descendant.

Y = Postorder

• Ancestor always follows descendant ✅
  ✔ Valid pair: (Pre, Post)

Y = Inorder

• Inorder does not guarantee ancestor after descendant ❌
  ✘ Not valid

Case 2: X = Inorder

• Inorder does not guarantee ancestor before descendant ❌
  ✘ No pair starting with Inorder is valid

Case 3: X = Postorder

• Ancestor appears after descendant ❌
  ✘ Cannot satisfy “m precedes n”

Final Answer

The only pair (X, Y) for which the statement holds is:

$$\boxed{{\displaystyle (X=\text{Preorder},Y=\text{Postorder})}}$$