50 votes 50 votes 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 $SQPTRWUV$ $SQPTUWRV$ $SQPTWUVR$ $SQPTRUWV$ DS gatecse-2014-set3 data-structures tree easy + – go_editor asked Sep 28, 2014 • edited Jun 29, 2019 by Lakshman Bhaiya go_editor 16.5k views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments VYAN_jy commented Nov 7, 2021 reply Follow Share ill formed question I must say. 2 votes 2 votes samir757 commented Dec 25, 2021 reply Follow Share For detailed explanation of the question , refer to the video below https://www.youtube.com/watch?v=XjggSKsOoes 3 votes 3 votes Shaikh727 commented Jul 29, 2022 reply Follow Share Thank you 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 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) Nitesh Singh 2 answered Jan 18, 2019 Nitesh Singh 2 comment Share Follow See all 2 Comments See all 2 2 Comments reply Sambhrant Maurya commented Nov 24, 2019 reply Follow Share Will the preorder and postorder traversal of a ternary tree be: Pre: Root, Left, Mid, Right Post: Left, Mid, Right, Root ?? 0 votes 0 votes Pranavpurkar commented Jul 27, 2022 reply Follow Share Sambhrant Maurya I think yes!! the change is only in the inorder traversals. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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). vaibhavkedia968 answered Sep 4, 2020 vaibhavkedia968 comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes It is not the regular inorder traverse we study but we can approach the question smartly here by looking the Options. INORDER Traversal has LEFT → NODE → RIGHT Option C is rejected as Node is at the last. Every Option has ‘SQP’ means S is traversed before Q. We can also apply the same logic with Node ‘U’ and ‘W’. W should be traversed before U. Now we will look in the Options Option B & D gets Rejected Using this logic. Correct Ans is Option A SarthakShastri answered Dec 27, 2023 SarthakShastri comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes In the tree walk: Visit Node first time: Pre Order “ ABDECFG” Visit Node Intermediate time: In order: “DBEAFCG” [ Intermediate is same as last visit, in some cases, like for ‘S’ ] [Better “ Second visit” for inorder] Visit Node Last time: Post order: “DEBFGCA” Applying this concept here, answer ‘A’ holds Walking the graph, is traveling through that red line, and visiting is touching the node and saying “Hi! there” Souvik33 answered Jan 25, 2023 Souvik33 comment Share Follow See all 0 reply Please log in or register to add a comment.