4.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$
in DS
edited | 4.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?
–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??)
+1
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
0
The first child of a node is considered as the left child so here S becomes left of Q.

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

by Boss (19.9k points)
edited by
+8
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??
+9
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??

0
what would be the the traversal order in terms of root middle left and right if pre ans post order was asked ?

in order traversal is ternary tree is left-> ROOT->middle->right .what will be pre and post for ternary tree? is there any patteen?
0
What would inorder traversal of n-ary tree look like?
+1

@PRK  see this link for pre order and post order for n-ary tree

https://leetcode.com/articles/introduction-to-n-ary-trees/

0

@Vicky Bajoria, by default if only one child is present in a tree and  it's considered left child, that's standard. I hope it solves your doubt even with node W.

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

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

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 ??

+2

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

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.

+1

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

0
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)
by (457 points)
+1 vote
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)
by Active (4.5k points)
0
Will the preorder and postorder traversal of a ternary tree be:
Pre: Root, Left, Mid, Right
Post: Left, Mid, Right, Root ??