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

De openkb
Aller à : Navigation, rechercher

Sommaire

Questions

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

    • How can I determine whether its preorder, inorder or postorder efficiently?
    • 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?

<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/Sorted_binary_tree_preorder.svg/220px-Sorted_binary_tree_preorder.svg.png" alt="Sample tree">

Answers

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. )

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/20439386/given-a-tree-traversal-order-find-out-whether-it-is-preorder-inorder-or-postorde

Related

Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Outils