HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Can the pre-order traversal of two different trees be the same even though they are different?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
cantheordersamethougharetreespredifferenttwo

Problem

This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal.

It is also mentioned that the in-order traversal of two different trees can be the same though they are structurally different. Is there an example of this?

Solution

Tree Examples (image):

A:                 B:
     ‾‾                 ‾‾
     1                  1
    /                  / \
   2                  2   3
  /  
 3


This is an example that fits your scenario, Tree A root׳s value is 1, having a left child with value 2, and his left child has also a left child with value 3.

Tree B root׳s value is 1, having a left child with value 2 and a right child with value 3.

In both cases the Preorder traversal is 1->2->3.

Code Snippets

A:                 B:
     ‾‾                 ‾‾
     1                  1
    /                  / \
   2                  2   3
  /  
 3

Context

StackExchange Computer Science Q#110738, answer score: 28

Revisions (0)

No revisions yet.