c++ - How to re-create tree whose inorder traversal is stored in the file

Question

A special type of tree is given, Where all leaf are marked with distinct symbols and all others nodes are marked with dummy character 0. every node can have 0 or at most 2 nodes. Trees inorder traversal is written to file. Please give a algorithm to build tree from this traversal.

Answer 1

the problem as explained in the question is unsolveable, because there can be more then one tree for a given in-order traversal, even if the leaves are well known. (in the example attached, the in order for both trees is 1,2,3,4,5 and 1,3,5 are leaves in both).

you might want to store both inorder traversal and pre-prder traversal, and from there, there is a simple recursive algorithm to reconstruct the tree:

reconstruct(List preOrder,List inOrder):
   if preOder.empty() == true:
          return nil
   root.value<-preOrder[0]
   left_in = inOrder.filter(left,root) (*) 
   left_pre = preOrder.filter(left,root) (*) 
   root.left = reconstruct(left_pre,left_in)
   right_in = inOrder.filter(right,root) (*) 
   right_pre = preOrder.filter(right,root) (*) 
   root.right= reconstruct(right_pre,right_in)
   return root

(*) the filter finds all elements left/right to the root (in the in-order) and returns it, for pre-order it returns the same set of nodes in-order returned, but as they appear in the pre-order list.

attached: example described above:

EDIT: added stop condition for the recursive algorithm.

EDIT 2:
the filter will look something like that (pseudo code) (assuming each element is unique):

inOrderFilter(list,root):
  i <- 0
  left <- [] (empty list)
  right <- []
  while (list[i] != root):
    left.add(list[i])
    i <- i+1
  while (i < list.size):
    right.add(list[i[)
    i <- i+1
  return pair(left,right)

preOrderFilter(list,left_in,right_in):
  left <- []
  right <- []
  for each e in list:
    if e in left_in:
       left.add(e)
    else if e in right_in:
       right.add(e)
  return pair (left,right)

basically, for the left_in you need everything left of the root, and for right_in you need everything right of the root (left and right according to the in order list).
for left_pre, and right_pre: you need a permutations of left_in,right_in, each of them should have the same elements that XXX_in has, but they should retain the order they had in the original pre-order.