0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Are you allowed to duplicate node labels? $\endgroup$
    – Raphael ♦
    Apr 1, 2017 at 7:37

1 Answer 1

Reset to default
-1
$\begingroup$

It is possible only If all nodes have same value.

Improve this answer
$\endgroup$
8
  • $\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, 2017 at 6:36
  • 1
    $\begingroup$ Please elaborate: why? $\endgroup$
    – Raphael ♦
    Apr 1, 2017 at 7:31
  • $\begingroup$ @YuvalFilmus Your statement is correct, but does not seem to relate to gurchet singh's post. $\endgroup$
    – Raphael ♦
    Apr 1, 2017 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, 2017 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, 2017 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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