# Strict-Binary Tree - Same Post-order & Pre-order sequences?

I'm going through some past exam papers for my course and I'm having trouble completing this one question.

It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order and post-order traversal sequence".

Is this actually possible? Wouldn't I need to visit the root node before anything else for both sequences, that isn't possible with post-order traversal in a strict binary tree right? Unless the tree consisted of a single node?

I assume I'm missing something obvious. Post-order = LRN, Pre-order = NLR.

• Are you allowed to duplicate node labels?
– Raphael
Apr 1, 2017 at 7:37

## 1 Answer

It is possible only If all nodes have same value.

• The order of nodes in pre-order and post-order traversal sequences depends on the structure of the tree, not on the values of the nodes. These traversal sequences make sense even if there are no values at all. Apr 1, 2017 at 6:36
• Please elaborate: why?
– Raphael
Apr 1, 2017 at 7:31
• @YuvalFilmus Your statement is correct, but does not seem to relate to gurchet singh's post.
– Raphael
Apr 1, 2017 at 7:32
• @YuvalFilmus The claim here is that $\operatorname{pre}(T) = \operatorname{post}(T)$ if and only if all labels of $T$ are the same. That is a valid statement -- the question is if it is true. If it is, it does answer the question: take any tree (structure) and label every node $1$. (In fact, that construction answers the question even if the reverse direction of the claim is false.)
– Raphael
Apr 1, 2017 at 7:37
• @YuvalFilmus But the resulting sequences do. For instance, the pre-order is sorted if the tree is a search tree, but usually not otherwise.
– Raphael
Apr 1, 2017 at 7:56