Answer the following questions: a) Let T be an ordered tree (i.e.. the children
ID: 3803789 • Letter: A
Question
Answer the following questions: a) Let T be an ordered tree (i.e.. the children of each node are ordered) with more than one node. Is it possible that the pre-order traversal of T visits the nodes in the same order as the post-order traversal? If so, give an example; otherwise argue why it cannot happen. Likewise, is it possible that pre-order traversal of T visits the nodes in the reverse order as post-order traversal? If so, give an example; otherwise argue why it cannot happen. b) Answer the previous questions if T is a proper binary tree with more than one node.Explanation / Answer
a)
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. Consider the case of a tree with only two nodes.
b)
It is not possible for the post and pre order traversals to visit the nodes of a proper binary tree in the same order for the same reason in the previous question.
It is not possible for the post and pre order traversals to visit the nodes of a
proper binary tree in the reverse order. Let x be the root of a proper binary
tree and let T1 and T2 be the left and right subtrees. A postorder traversal
would visit the postorder traversal of T1, the postorder traversal of T2 and then
node a while the preorder traversal would visit node x, the preorder traversal
of T1 and then the preorder traversal of T2. Clearly the postorder and preorder
traversals cannot be the reverse of each other since in both cases, all the nodes
of T1 are visited before all the nodes of T2.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.