Today we continue the set of coding exercise with different orders of traversal. This time we include levelwise traversal with InOrder. Again we fallback on our argument that the left and right tree need to be separated by root node in at least one sequence to make it easier for the tree to be rebuild.

                    A

             B            C

        D      E          F     G

H    I    J    K         L   M    N    O
Pre:     A  B  D  H  I  E  J  K  C  F  L  M  G  N  O
Post:    H   I   D  J   K E B  L  M F N   O  G  C   A
In:       H   D   I  B   J  E K A  L  F M   C  N  G   O

Level  NULL A  NULL B  C  D  NULL  E F G  H  NULL I   J  K  L M  N   O NULL

We iterate the nodes level wise so we know that the parents are traversed before the children are.
for any node we try to rebuild, we have the inorder give us the left-subtree +  root  + right-subtree going forward. Each sub-tree is found till a node upto a parent . For example, E has sub trees in the inorder upto B on one side and upto A on the other side. A has subtrees to the extremes because it is the root. The siblings are found in their respective subtrees as occuring in the next level.


Node Rebuild(List<Node> level, List<node> in) // All nodes in list initialized with left and right = null and set only with data
{
assert( level!= null && in != null);
assert (level.Count() == in.Count());

for(int i =  level.Count(); i > 0; I--)
{
     Node root = level[I];
     int inIndex= Array.indexOf(in, level[i]);
     Node left = in.First( x => Array.indexOf(level, x) < i);
     Node right = in.First( x => Array.indexOf(level, x) > i );
     int left = Array.indexOf(in, left);
     int right = Array.indexOf(in, right);
     int left-tree-len = inIndex - left - 1;
     int right-tree-len = inIndex - right - 1;
     Node leftSibling = findNextLevelOccurrenceFromSubtree( level, in,  i, left, -1, inIndex);
     Node rightSibling = findNextLevelOccurrenceFromSubtree(level, in, i, -1, right, InIndex);
     root.left = leftSibling;
     root.right = rightSibling;
}
return level[0];
}

Node findNextLevelOccrrenceFromSubtree(
           List<Node> level, // the level list
           List<Node> in, // the in list
           int current, // the index in level of the current element
           int left, // left most position of subtree in inorder
           int right, // left most position of subtree in inorder
           int inIndex, // left most position of subtree in inorder
           )
{
while( current != null) current++;
current++;
if (left > 0){
for (int i = inIndex; i >= left; i--) // left subtree only
      for (int j = current; j != NULL; j++)  // next level only
     if (in[i] == level[j])
         return in[i];
}
if (right > 0)
{
for (int i = inIndex; i <= right; i++) // left subtree only
      for (int j = current; j != NULL; j++)  // next level only
     if (in[i] == level[j])
         return in[i];
}
 return NULL;
}