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

graph-theory tree-traversal preorder postorder
Omid7 picture Omid7 · Apr 7, 2013 · Viewed 7.8k times · Source

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?

Answer

ggbranch picture ggbranch · Apr 7, 2013

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.

Related questions

Best algorithm for detecting cycles in a directed graph

What is the most efficient algorithm for detecting all cycles within a directed graph? I have a directed graph representing a schedule of jobs that need to be executed, a job being a node and a dependency being an edge. …

Read More
When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?

I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other? Could anyone give any examples of how DFS would trump BFS and vice versa?

Read More
Finding all cycles in a directed graph

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node? For example, I want something like this: A->B->A A->B->C->A but not: B-&…

Read More