2.4k 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$
edited | 2.4k 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?
0
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.

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

edited by
+5
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??
+7
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

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

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.
For inorder traversal you can take a trick
whenever you visit the node second time take it into inorder sequence.. :D
0
Is there such trick for other traversals as well, they may come in handy when solving for n-ary tree. @ankit srivastava
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)
OPTION C IS RIGHT
+1
Answer is option A). You are doing some mistake. Please check one more time.