Given a tree traversal order find out whether it is preorder inorder or postorder

1
votes

Assuming that someone gives me a tree traversal order for the nodes from A to G - F, B, A, D, C, E, G, I, H which can be either preorder, inorder or postorder

  1. How can I determine whether its preorder, inorder or postorder efficiently?
  2. How do I reconstruct the tree efficiently without having to construct the tree for each of the three traversal types like the one shown below?

Sample tree

1
treetree-traversal

1 Answers

0
votes

Assuming the tree traversal given to you is accurate--

if you do not have any info on "what kind of tree", there's no way you can tell what kind of traversal it is.

if you are given info about the tree and how the values are organized, you possibly can.

if it is a binary tree, and if:

  • the list is perfectly ordered, it is definitely in in-order

  • the list is not ordered and some value which is not minimum in the list is the first value, it is definitely in pre-order (that first value is the root)

  • the list isn't ordered and the first value is minimum. it is definitely in post-order.

Given the traversal of a binary tree,

if in-order : there is more than one tree that results in that in-order traversal .

if pre-order: exactly one tree corresponding to it (the first in a list is always the root of that subtree, the values less than root are in left-subtree and greater than are on the right)

if post-order: exactly one subtree (similar to pre-order above. )