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. $\text{SQPTRWUV}$
• B. $\text{SQPTUWRV}$
• C. $\text{SQPTWUVR}$
• D. $\text{SQPTRUWV}$

Comments

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

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

---

Thank you

---

Assuming
Any representation needs to be consistent, and our biggest helpers are Q-S and U-W, 
By consistent I mean if in Q-S( we assume S to be left child of Q) then in U-W(W must also be left child of U).
So we boil down to three possibilities here, either be left child(L), middle child(M) or Right child(R). 
Preorder -> Root->Left->Middle->Right
Postorder-> Left->Middle->Right->Root
Inorder there isn't any standard 
So 

 Left->Root->Middle->Right

 Left->Middle->Root->Right

 

 

Answer 1

Correct Option: A

The inorder traversal order of a ternary tree is left $\rightarrow $ root $\rightarrow $ middle $\rightarrow $ right.

Comments

@Lakshman Bhaiya how we are taking W as the left subtree of U any specific reason. If we take W as right subtree of U answer is coming ( D ) correct me if i am wrong

---

It's not a binary tree it's a ternary tree, so we don't have a specific rule.

See this: https://cs.stackexchange.com/questions/98891/inorder-traversal-of-the-ternary-tree

---

this kind of question do we get bonus marks

Answer 2

The inorder traversal of a ternary tree is given by Left > Root > Middle > Right.

But if you apply this traversal sequence on this tree, the order is SQPTWURV.

According to the answer given by various books, the answer is (A).

(A) can only be the answer if we consider 'S' to be the left child of 'Q', and 'W' to be the left child of 'U'.

Comments

Here order will not start from S as well. It will start from Q because S is the middle element which will come after root element Q.

---

I think the examiner designed the option to suggest that, if a node has only one child, then it left child. Therefore, S comes before Q and W comes before U in inorder traversal of the given tree.

Answer 3

For inorder traversal you can take a trick
whenever you visit the node second time take it into inorder sequence.. :D

Comments

@Lakshman Patel RJIT Can you tell what will the the preorder and postorder of this tree?

---

@Sambhrant Maurya

see this  1  2

---

You should check out RBR videos on this topic. You will never miss one question from here.

Answer 4

Inorder transversal of ternary tree is :- left -> Root->Middle->Right

from the given figure, it is not clear whether W is middle child of U or left child of U

if W is middle child of U then  SQPTRUWV (option D)

if W is left child of U then       SQPTRWUV  (option A)

Comments

“The inorder traversal of a ternary tree is given by Left > Root > Middle > Right.””

Ok this is general for this.

What if question is about Post and pre traversal , are they 

    pre: root-middle-left-right

   post :left-right-root-middle 

Someone conform it? How it will go for other trversal

 

Answer 5

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 6

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).