patternMajor
Can the pre-order traversal of two different trees be the same even though they are different?
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?
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):
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.
A: B:
‾‾ ‾‾
1 1
/ / \
2 2 3
/
3This 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
/
3Context
StackExchange Computer Science Q#110738, answer score: 28
Revisions (0)
No revisions yet.