9. There are three different tree traversals for binary trees, which are in-order traversal, pre-order traversal and post-order traversal. If pre-order traversal and post-order traversal are provided,...

Extracted text: 9. There are three different tree traversals for binary trees, which are in-order traversal, pre-order traversal and post-order traversal. If pre-order traversal and post-order traversal are provided, it is found that in some cases, the in-order traversal is not unique. Construct an example, with exactly 3 nodes, that pre-order traversal and post-order traversal can give a unique in-order traversal. Construct another example, with exactly 3 nodes, that pre-order traversal and post-order traversal cannot give a unique in-order traversal. c. State and explain the necessary and sufficient condition that a unique in-order traversal can be deduced from given both pre-order traversal and post-order traversal.