1

A multiway tree T can be represented as a binary tree T~ by using the firstChild and nextSibling pointers. If we think of the firstChild link as being the left link and the nextSibling link as being the right link, then we can traverse this binary tree T~ as we would any binary tree.

A preorder traversal of T~ is equivalent to which of the following traversals of T? Pre- order, postorder, neither.

An inorder traversal of T~ is equivalent to which of the following traversals of T? Pre- order, postorder, neither.

A postorder traversal of T~ is equivalent to which of the following traversals of T? Pre- order, postorder, neither.

There is no order of left or right child in multiway tree.. so basically one tree structure can have different preorder post order and inorder traversals. So no order can be equivalent to any. Am I correct??

girl101
  • 333
  • No: the mere fact that you can talk about firstChild and nextSibling tells you that you’re dealing with an ordered tree (also called a plane tree), i.e., one in which the children of each non-leaf are ordered (e.g., from left to right). – Brian M. Scott Oct 26 '14 at 04:57
  • So in that case the preorder of T will be equal to preorder of T~ and postorder will be equal to post order and so on... How can they be different since the order is maintained in both the trees?? – girl101 Oct 26 '14 at 05:00
  • I believe that the two preorder traversals give the same result, but not the two postorder traversals. – Brian M. Scott Oct 26 '14 at 05:06
  • I took an example I am getting both the post orders same... Sir if possible can you tell me why you said so? Probably I am missing out on something.... – girl101 Oct 26 '14 at 05:13
  • Start with a tree that has a root $a$ with children $b$ and $c$ in that order, where $b$ has one child, $d$. Postorder traversal gives you $dbca$. The corresponding binary tree has root $a$ with left child $b$; $b$ has left child $d$ and right child $c$. Postorder traversal gives you $dcba$, which is not the same as before. – Brian M. Scott Oct 26 '14 at 05:17
  • So basically the inorder and postorder traversals change, only pre order traversal is the same for T and T~ – girl101 Oct 26 '14 at 05:22
  • I don’t think that you can even sensibly define inorder for arbitrary ordered trees: it depends on the fact that each node has at most two children. – Brian M. Scott Oct 26 '14 at 05:25
  • Can you please elaborate what you are trying to say? Why cant we nt define inorder?? Cant we define it the same was as we did for postorder and preorder?? – girl101 Oct 26 '14 at 05:30
  • If your tree has a root $a$ with children $b,c$, and $d$, in that order, what do you think is the inorder listing of the nodes? – Brian M. Scott Oct 26 '14 at 05:32
  • bacd , as the very first child is the left child and the rest are the right child – girl101 Oct 26 '14 at 05:40
  • You can do it that way, but it’s pretty arbitrary; one could equally well place the parent just before the last child, and I can think of at least one other reasonable definition. But yes, if you have that definition, then you’re quite right: the two inorders need not be the same (and that tree is an example). – Brian M. Scott Oct 26 '14 at 05:43
  • How can you place the parent just before the last child? That is not the rule for inorder traversal, isnt it so?? – girl101 Oct 26 '14 at 05:49
  • That depends entirely on how you define inorder traversal. I have previously seen it defined only for binary trees. If you’ve been given a definition for arbitrary ordered trees, that’s fine, and you should use it; I’m just pointing out that there is more than one reasonable way to generalize the definition from binary trees to arbitrary ordered trees, and that the idea really doesn’t make a lot of sense in the more general context, since the choice of definitions is pretty arbitrary. – Brian M. Scott Oct 26 '14 at 05:51
  • Ok Ok, Now i get it. – girl101 Oct 26 '14 at 05:54

0 Answers0