The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
3.5k views

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

  1. $SQPTRWUV$
  2. $SQPTUWRV$
  3. $SQPTWUVR$
  4. $SQPTRUWV$
asked in DS by Veteran (97.7k points)
edited by | 3.5k views
0
@Arjun sir:

where to find such questions? where should i read this from?

and in exam if such questions, wont it be better not to attempt unless we know the exact algorithm?
–1
Option D will be correct (even if S is considered to be the left child of Q)

.I am getting the option D as the answer . plz explain

( If W is the left child of U,then it cud be the answer??)
0
QSPTRUWV, please correct me if i am wrong.
0

When I was studying using NPTEL videos by IITD (by Dr. Naveen Garg), I wrote down in my notes that inorder traversal is only applicable for binary trees; not applicable for generic trees wherein the degree of nodes is greater than $2$. But, I am not sure whether the professor actually said so, or it was what I understood. Any comments?

For this problem, I considered both traversal sequence (given below), and ended up getting $A$ as the answer. Is this approach correct?

  1. $T - R - \text{(subtree U-V)}$
  2. $T - \text{(subtree U-V)} - R$

 

0

Geeksforgeeks has given  the answer to this as A.

https://www.geeksforgeeks.org/gate-gate-cs-2014-set-3-question-22/

6 Answers

+34 votes
Best answer

(A)  the inorder traversal order of a ternary tree is left $\rightarrow $ root $\rightarrow $ middle $\rightarrow $ right.

answered by Boss (19.9k points)
edited by
+6
S is middle subtree of Q or left subtree..?? As per the answer they have assume it as left subtree.. why?? visually it seems middle subtree.. so middle subtree can not come with empty left subtree?? is this rule??
+8
IDK about that rule... But then looking at the options it clear that it must be a left child only.
0
what is the inorder traversal of a 4-ary tree?
0
@Susgmita It will depend on how tree is and which type of sequence is given. If it's having numerical sequence then it will be a sorted array in ascending order
0

@ according to Inorder

preorder should be root-left-middle-right  & postorder should be left-middle-right-root.

Is that corect??

+10 votes

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

answered by Loyal (9.2k points)
0
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.
0
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.
+6 votes
For inorder traversal you can take a trick
whenever you visit the node second time take it into inorder sequence.. :D
answered by Junior (891 points)
0
Is there such trick for other traversals as well, they may come in handy when solving for n-ary tree. @ankit srivastava
0

Yes

Preorder: When you visit the node the first time we can print the node

In order: When you visit the node the second time we can print the node

Postorder: When you visit the node the third time we can print the node

0

                                        F

                            /         \

                        /                \

                     G                   H

@Lakshman Patel RJIT : for post order it is not clear, how do we visit G & H third time, we could only visit second time, can yiu explain ??

+1

Yes,see this

0
ya, thanx
0
The trick is right for binary but how to deal with n-ary (just like this question which is ternary)? Thanks :)
0

@Lakshman Patel RJIT How to use dummy nodes in n-ary trees (n>2) like in this question?

0

@

this trick will work for a binary tree.

It's good to follow the actual procedure.

If you have some question than apply similar to a binary tree and check it out.

+3 votes
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)
answered by (307 points)
0 votes
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)
answered by Active (2k points)
–1 vote
OPTION C IS RIGHT
answered by (17 points)
+1
Answer is option A). You are doing some mistake. Please check one more time.
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,811 questions
54,533 answers
188,417 comments
75,580 users