Working with Ordered Trees Example problem and solution Question: Suppose we let

Question

Working with Ordered Trees

Example problem and solution

Question: Suppose we let T be an ordered tree with more than one node. Is it possible that the preorder traversal of T visits the nodes in the same order as the postorder traversal of T? If so, give an example; otherwise, argue why this cannot occur. Likewise, is it possible that the preorder traversal of T visits the nodes in the reverse order of the postorder traversal of T? If so, give an example; otherwise, argue why this cannot occur.

Answer: It is not possible for the postorder and preorder traversal of a tree with more than one node to visit the nodes in the same order. A preorder traversal will always visit the root node first, while a postorder traversal node will always visit an external node first.

It is possible for a preorder and a postorder traversal to visit the nodes in the reverse order. An example is the case of a tree with only two nodes.

You try it

Question: Answer the previous question for the case when T is a proper binary tree with more than one node.

Explanation / Answer

Answer for Question:

Example: consider the below Binary Tree
X
/  
Y

or

X
  
Z
      
Post-order traversal visits the nodes in the order
left-right-root and pre-order visits the nodes in the
order of root-left-right. In order for them to produce
the same output, "left" must be equals to "root", which
just doesn't make sense.
With the above example, pre-order will produce XY or XZ
respectively and post-order will produce BA and ZX.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.