GATE CSE 2014 Set 3 | Question: 12

Question

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

• A. $SQPTRWUV$
• B. $SQPTUWRV$
• C. $SQPTWUVR$
• D. $SQPTRUWV$

Comments

ill formed question I must say.

---

For detailed explanation of the question , refer to the video below

https://www.youtube.com/watch?v=XjggSKsOoes

---

Thank you

Answer 1

Inorder Traversal: Left, Root, Middle, Right.

If single child is given of a node then First child of the node is considered as the left child so here S becomes left child of Q.

so answer will be option (A)

Comments

Will the preorder and postorder traversal of a ternary tree be:
Pre: Root, Left, Mid, Right
Post: Left, Mid, Right, Root ??

---

Sambhrant Maurya

 I think yes!! the change is only in the inorder traversals.

Answer 2

Since left subtree of P is giving SQ (note that all options start with SQ), middle subtree of R has to give WU (because structure is same). Also, knowing the algorithm of ternary inorder traversal (left →→ root →→ middle →→ right as mentioned in the best answer), we can conclude that both S and W are indeed the left child of Q and U respectively. This rules out option B and D. Option C is also ruled out because R cannot come at the end of an inorder when it is having its right child. So, only option A is left, which is the answer.

The thing is, you may know the algorithm for ternary inorder, but still the question can remain unclear, and then you have to come up with the answer using the options given (finding what is “common” among all the options).

Answer 3

It is not the regular inorder traverse we study but we can approach the question smartly here by looking the Options.

INORDER Traversal has LEFT → NODE → RIGHT
Option C is rejected as Node is at the last.

Every Option has ‘SQP’ means S is traversed before Q.
We can also apply the same logic with Node ‘U’ and ‘W’.
W should be traversed before U.  Now we will look in the Options
Option B & D gets Rejected Using this logic.

Correct Ans is Option A

Answer 4

In the tree walk:

1. Visit Node first time: Pre Order “ ABDECFG”

2. Visit Node Intermediate time: In order: “DBEAFCG”  [ Intermediate is same as last visit, in some cases, like for ‘S’ ]  [Better “ Second visit”  for inorder]

3. Visit Node Last time: Post order: “DEBFGCA”

Applying this concept here, answer ‘A’ holds

Walking the graph, is traveling through that red line, and visiting is touching the node and saying “Hi! there”