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.

  • $\begingroup$ Are you allowed to duplicate node labels? $\endgroup$ – Raphael Apr 1 '17 at 7:37

It is possible only If all nodes have same value.

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 1 '17 at 6:36
  • 1
    $\begingroup$ Please elaborate: why? $\endgroup$ – Raphael Apr 1 '17 at 7:31
  • $\begingroup$ @YuvalFilmus Your statement is correct, but does not seem to relate to gurchet singh's post. $\endgroup$ – Raphael Apr 1 '17 at 7:32
  • 1
    $\begingroup$ @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.) $\endgroup$ – Raphael Apr 1 '17 at 7:37
  • 1
    $\begingroup$ @YuvalFilmus But the resulting sequences do. For instance, the pre-order is sorted if the tree is a search tree, but usually not otherwise. $\endgroup$ – Raphael Apr 1 '17 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.