0
$\begingroup$

According to wikipedia , Definition of In-order Traversal on Binary Tree :-

1) Check if the current node is empty or null.
2) Traverse the left subtree by recursively calling the in-order function.
3) Display the data part of the root (or current node).
4) Traverse the right subtree by recursively calling the in-order function.

I want to find the similar In-order Traversal definition on Ternary Tree. I was referring the Professor Robert Sedgewick's lecture of Ternary Search Tries. I found that if I do the In-order traversal on the Ternary Search Tree(a type of Trie data structure) for a particular searched string then visiting order of nodes should be :-

1) Check if the current node is empty or null.
2) Traverse the left subtree recursively calling in-order function.
3) Display the data part of the current node.
4) Traverse the middle subtree by recursively calling the in-order function.
5) Traverse the right subtree by recursively calling the in-order function.

Now , while solving one homework problem , I got different result from the given solution. The problem was :- Find the In-order Traversal of the following tree :-

enter image description here

According to me answer should be :- AKBJCLIEDHFG
But given answer is :- AKBJCLIDEHFG

I also faced one similar question in one competitive exam as :-

enter image description here

According to me , Answer should be :- $QSPTRUWV$
But given answer is :- $SQPTRWUV$
Please verify whether my answers are correct or not and If I am wrong somewhere then please correct me.

$\endgroup$
0
$\begingroup$

According to me answer should be :- AKBJCLIEDHFG

Your answer is ((A) (K) ((B) (J) (C))) (L) (I) (((E) (D)) (H) (F) (G))

Please take a close look at the part ((E) (D)). Here lies the ambiguity/confusion/uncertainty. The ambiguity is whether D is the left subtree or the middle subtree or the right subtree of E.

Because of the limited drawing spaces that shows the tree, it can be argued in a few ways. I could swear that D is meant to be the left subtree or E. On a different day, I might, agreeing with you, insist that D is so apparently the middle subtree of E. On another day, I could stretch myself a little bit, unabashedly claiming that D is in fact the right subtree of E. Unless there are some kind of instructions such as your textbook or whatever material you have been using has defined the rules how to tell the class of subtree from the way is drawn in case of ambiguity, it is impossible to conclude which subtree of E D is.

So your question is reduced to whether there are those kind of rules in your material. Or in your instructor's notes or oral guide. Or, what is general convention in your culture or your context to interpret "left", "middle" and "right". This question is not so much of computer science, but more about linguistics and drawings and culture.

If I had to pick one solution out of no context, I would be very frustrated on deciding whether D is a left subtree or right subtree of E. I would choose one of many possible actions below, without any particular preference.

  • try finding the context or the rules.
  • just choose left subtree.
  • just choose middle subtree.
  • wave my hands, declaring no value to solve a question that is not well-formed.
  • presenting two solutions or three solutions, each with its assumption stated clearly.
  • redraw the graph in the question.
  • raise a question about that question to seek other's judgements as you just did
  • had I been a student, my TA should have been my savior and my professor should have been the ultimate arbitrator.
  • the last option that stands for all the remaining possibilities.

(By the way, I just searched the lecture briefly. I have not found any definitive guide on how to tell left or middle or right subtree. Of course, I might have missed some hints or conspicuous rules.)

$\endgroup$
  • $\begingroup$ Thank you so much for all your efforts for writing the answer. Actually, I have not found any good reference regarding In-Order Traversal of ternary tree. After watching the lecture , I concluded that in-order traversal is like Left-Root-Middle-Right because in the given examples by speaker of that lecture , after in-order traversal on the tree, I was getting the same searched string like binary search tree. $\endgroup$ – ankit Oct 22 '18 at 5:29
  • $\begingroup$ Sir , Can you please tell me that Is there any standard rule for In-order Traversal of ternary tree or not like in binary tree , we follow Left-Root-Node ? and is this rule valid if a node has only one middle link like in above example ? $\endgroup$ – ankit Oct 22 '18 at 5:34
  • $\begingroup$ If there is a standard rule or if there has been enough interest in a standard rule, it should have shown up at its Wikipedia entry. Since that entry is empty, I will give myself or my TA some leeway to define the in-order traversal of ternary tree as reasonable as we can. Since it is usually said the middle subtree is extending its parent in a unbiased way, that is, neither smaller or greater, Left-Root-Middle-Right should be a very reasonable if not the best or only rule for an in-order traversal of ternary tree. $\endgroup$ – Apass.Jack Oct 23 '18 at 0:50
  • $\begingroup$ In fact, as far as I can find, Geekforgeeks or Sanfoundary, **Left-Root-Middle-Right ** showed up for ternary tree traversal. $\endgroup$ – Apass.Jack Oct 23 '18 at 1:25
  • $\begingroup$ Here is my conclusion. This is a minor question. We have most if not all the relevant information here. There is very little value to dig deeper. Left-Root-Middle-Right is expected. How to view a leaf node which is the single child of its parent node, as left, middle or even right subtree, is somewhat arbitrary, situational and subjective when its order relationship with its parent, that is, <, =, or >, is not explicitly specified. $\endgroup$ – Apass.Jack Oct 23 '18 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.