Creating a tree from pre-orders and post-operations

Question

If I have preorder and postorder traversals, can I build a tree that is not necessarily a binary tree? Sort of:

Pre order: KLMOPN

Post Order: LOPMNK

Addition:

   K
 / | \
L  M  N
  / \
 O   P

I read that this is impossible without mutual traversal for binary trees, but is it possible to do this only with traversals of order and postorder for a nonbinary tree?

Answer 1

If the tree runs in nodes (provided that it has a 3 node tree, left, middle, right). You must 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);

}

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

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

, .