CODEWITHSUNDEEP
graph-theorytree-traversalpreorderpostorder
Omid7
Omid7

Reputation: 3194

Is it possible the pre-order traversal be the same order as the post-order traversal?

If T be an ordered tree with more than one node. Is it possible the pre-order traversal of T visit the nodes in the same order as the post-order traversal of T? if "yes" can you please give an example. And if "No" could you please explain why it cannot occur?

Upvotes: 1

Views: 10197

Answers (2)

Makoto
Makoto

Reputation: 106390

In general cases, the leaves of a tree are unique, and as such, should appear in opposite manners if you're performing a pre- or post-order traversal.

However, I can see two cases in which the pre- and post-order traversals are the same: Singleton and duplicate elements.

With a singleton, you only have the one node, so it doesn't matter if you visit it before or after looking for zero leaves.

What if you had a tree with duplicate elements in it? If the insertion strategy was to accept any element greater than or equal to the root node, then they would appear as a degenerate tree to the right:

 A
  \
   A
    \
     A
      \
       A

If it were less than or equal to the root node, you'd still have a degenerate tree, but to the left.

Now, if your insertion strategy was to discard duplicate elements, you would be left with the singleton case, which still has the pre- and post-order traversals resulting in the same elements.

Upvotes: 2

ggbranch
ggbranch

Reputation: 559

Unless I'm missing something painfully obvious, the answer would be no. A ordered tree with > 1 node (say for example, 2 nodes) will look like this.

    A    
 B

or

    A
        C

Post-order traversal visits the nodes in the order left-right-root and pre-order visits the nodes in the order of root-left-right. In order for them to produce the same output, "left" must be equals to "root", which just doesn't make sense. With the above example, pre-order will produce AB or AC respectively and post-order will produce BA and CA.

Upvotes: 1

Related Questions