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
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?
https://www.geeksforgeeks.org/gate-gate-cs-2014-set-3-question-22/
(A) the inorder traversal order of a ternary tree is left $\rightarrow $ root $\rightarrow $ middle $\rightarrow $ right.
@Gate Keeda according to Inorder
preorder should be root-left-middle-right & postorder should be left-middle-right-root.
Is that corect??
@PRK see this link for pre order and post order for n-ary tree
https://leetcode.com/articles/introduction-to-n-ary-trees/
@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'.
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
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 ??
Yes,see this
@Lakshman Patel RJIT How to use dummy nodes in n-ary trees (n>2) like in this question?
@Sambhrant Maurya
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.
@Lakshman Patel RJIT Can you tell what will the the preorder and postorder of this tree?
see this 1 2