# 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 '17 at 7:37

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 '17 at 6:36
• @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.)