1
$\begingroup$

As per Wikipedia, Algorithm for In-order Traversal of Binary Tree

  1. If the current node is empty/NULL/None return nothing.
  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 was interested in Algorithm for In-order Traversal of Ternary Tree. Upon referring 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.

But I got result different from claimed in one Assignment Problem, and in one Competitive Exam Problem.

Problem 1 : Find the In-order Traversal of the following tree Assignment

  • Mine Answer : AKBJCLIEDHFG
  • Given Answer : AKBJCLIDEHFG

Problem 2 : Consider the rooted tree with the vertex labelled P as Root. Find the order in which nodes are visited during an in-order traversal of the tree. Competitive Exam

  • Mine Answer : QSPTRUWV
  • Given Answer : SQPTRWUV

Please verify whether my answers are correct or not and If I am wrong somewhere then please correct me.

$\endgroup$

2 Answers 2

1
$\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$
9
  • $\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, 2018 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, 2018 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$
    – John L.
    Oct 23, 2018 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$
    – John L.
    Oct 23, 2018 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$
    – John L.
    Oct 23, 2018 at 1:34
0
$\begingroup$

A tree is a finite set of one or more nodes such that there is one specially designated node called the root node of the tree, and the remaining nodes are partitioned into trees $T_1,\ldots,T_k$ (called the subtrees of the root), where $k\ge0$.

Given a tree with a root node $n$ and subtrees $T_1, T_2, \ldots, T_k$, the inorder listing of the nodes of the tree is the list of nodes of $T_1$ in inorder, followed by $n$, followed by the list of nodes of $T_2, \ldots, T_k$, with the nodes in each group listed in inorder. Note that trees are also called ordered trees because the order in which the subtrees are mentioned does matter.

Thus, if you have a tree with a root node $E$ and a single child $D$, then the inorder listing would be $D,E$ because the first subtree $T_1$, which consists of the single node $D$, would be listed before the root node $E$.

We need to be clear on the definition of a tree (aka ordered tree) and the definition of a binary tree (which is not a special case of a tree; in fact, trees must be nonempty whereas a binary tree can be empty). Also, the inorder definition for a binary tree is different from the inorder definition of a tree. When you are given a binary tree, it must be specified whether a unique child is a left child or a right child, whereas in a tree a unique child would be (the root of) the first subtree.

A good reference for the definition of trees is [Knuth, "The art of computer programming, volume 1"] and for the definition of inorder traversal of (ordered) trees is [Aho, Hopcroft and Ullman, "Data structures and algorithms", Section 3.1].

$\endgroup$

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.