Building a tree from preorder and postorder traversals

Question

If I have the preorder and postorder traversals, can I construct a tree that isn't necessarily a binary tree? Something like:

Pre-order: KLMOPN

Post-order: LOPMNK

Build:

   K
 / | \
L  M  N
  / \
 O   P

I've read that this is not possible without inorder traversal for binary trees, but is it possible to do it with just preorder and postorder traversals for a non-binary tree?

Assuming the Q in post order was actually ment to be an O? Also, the O and P what are they branching off of? all 3? or one letter inpeticular — Lain
possible duplicate of reconstructing a tree from its preorder and postorder lists — Bernhard Barker

Lain Lain · Accepted Answer · 2014-02-23T05:02:33

If the tree is done in nodes (assuming its a 3 node tree, left, middle, right). You would write a recursive function.

Void Transverse(Node n){
if( n.left ==null && n.middle==null && n.right ==null){
 System.out.print(n.value);
 return;

}
Transverse(left);
Transverse(middle);
Transverse(right);
System.out.print(n.value);

}

That is some pseudo code(I will assume the OP comes from M). This will print out LOPMNK from the tree you showed.

k->L(printsL)->k->M->O(Print O)->M->P(Print P)->M(prints M)->k->N(prints N)->k(Print k).

Is the order it will happen in.

Building a tree from preorder and postorder traversals

1 Answers