Convert Preorder listing of a binary tree to postorder and vice versa
Solution 1
Without assuming that nodes in the tree have a field that idenrify themselves as internal or leaf, you can't find a unique answer for your question. That assumption or inorder listing must be available to find a unique tree. In this case, to find one possible answer, you can construct a tree of the form shown below to match any given postorder listing: (suppose postorder listing is: 1 2 3 4 5 6 7 8 9)
9[7[5[3[1,2],4],6],8]
Now you can make preorder listing using this tree.
Assuming nodes in the tree have a field that identify themselves as internal or leaf, we can make a unique tree out of a postorder listing for this kind of trees with this algorithm:
- Sweep from the beginning of the postorder list and find the first internal node. This node will have exactly two leaf children which precede this node in postorder listing.
- In your tree structure add that internal node and make two preceding nodes in the listing its children.
- Remove those two children from listing and make that internal node a leaf.
- Go to step 1 and repeat until listing becomes empty.
Solution 2
Consider the recursive structure of a preorder traversal:
T(r) = [r, T(r->left), T(r->right)]
where T(r) is the preorder traversal of tree rooted at node r
Then we know that the root of a tree described by T(r) is always the first node in the traversal.
Knowing this, and knowing that a root is always higher in a tree than its subtrees, think about how you would use this information to rebuild the tree. Think recursively.
Caveat: this can only be done if this is a binary search tree, which constrains nodes such that left-child < root < right-child
. In general, trees cannot be reconstructed from a single traversal. See this excellent resource for a more detailed explanation.
Ambiguity still exists regardless of the rule about 0 or 2 children:
4
/ \
2 5
/ \ / \
1 3 6 7
4
/ \
2 7
/ \
1 3
/ \
5 6
Both have the preorder traversal [4 2 1 3 5 6 7]
Solution 3
For example: you are required to convert postorder form to preorder form.this can be done in the following way. post order: DEBFCA preorder: ABDECF we see that A is the root. and from preorder we can determine that the node B is left to A.therefore we create two subclasses that are (BED) (CF).now when we traverse B we take it as a root and we see that after B, D IS PRESENT ,it means D is left to B and E is right to B .now we traverse C.take it as a root.then F is present after C so it is taken as left.
Jaelebi
Updated on June 04, 2022Comments
-
Jaelebi almost 2 years
How can I find the preorder listing of a tree if only the postorder listing is given and vice versa. Also, in the tree, every non-leaf node has two children (i.e. Each node has either two or zero children.)
EDIT: Another given assumption is that the label of each node is unique and has a field that will identify it as an internal node or a leaf. I think that ought to get rid of the ambiguity of a single preorder or postorder being able to uniquely identify a tree.