Inorder Traversal of the Ternary Tree

Question

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

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

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

Answer 1

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

Answer 2

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