Today we look at another coding problem along the same lines as the one we have seen in the previous post and the one before.
This time we have

// Postorder   C D B F E A
// Inorder       C B D A E F
// Build tree

We use relative comparisons which has worked for us before. Let us take the example of  our elemental subtree of a root with two siblings.
   J
K  L

1) All three nodes
    Post: K L J
    InOrder: K J L
2) Only left -subtree
    Post: K J
    In: K J    // L is missing because the previous element in post order lies within inIndex < that of J
3) Only right-subtree
    Post: L J
     InL J L  // K is missing when no elements appear before J whose inIndex < that of J
4) only root
Post:     Prev root Next
In :        Prev some-others root yet-others Next
4) is not differentiable from 2)

In general, with arbitrary sub-trees  for siblings
// left-subtree missing when
Previous node in pre appears to the rightof inIndex of root in inorder
// right-subtree missing when
previous element is left subtree in post order.

the sizes of the left and right sub tree can be kept track of because we use the same predecessor technique

                    A

             B            C

        D      E          F     G

H    I    J    K         L   M    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

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

for(int i =  post.Count()-1; I >= 0; I--)
{
Node root = post[i];
int inIndex= Array.indexOf(in, post[i]);
if ( I > 0 && I < post.Count())
{
//todo
int inIndexPrev = Array.indexOf(in, post[I-1]);
// Ignore comments below
// Ignore : Instead of taking subtree lengths, can we detect if subtrees are null from pattern
//Ignore: int inIndexNext = Array.indexOf(in, post[I+1]);
//Ignore: if both left and right subtree is null, handle it separately,
// Ignore: if (in.Count() - 1 - inIndex > 0)
// Ignore:if (inIndexPrev < inIndex && inIndexNext > inIndex)  continue;
//otherwise keep track of right subtree length as the differences in inorder indexes

     Int parent = findParentIndex (Post, i); //parent occurs to the right of root in post with left,right set
     Int parentin = Array.indexOf(in, post[parent]); // defaults to in.Count()
     Int righttreelen = parentIn-inIndex-1;
     if (i-righttreelen-1 > 0)
          Root.left = post [i-righttreelen-1];
     Int right = i-1;
     if (right > 0)
         Root.right = post [right];

}
return post[post.Count() - 1];
}

The recursive solution online is as follows:
public TreeNode buildTree(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd)
return null;

int rootValue = postorder[postEnd];
TreeNode root = new TreeNode(rootValue);

int k = 0;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == rootValue) {
k = i;
break;
}
}

root.left = buildTree(inorder, inStart, k - 1, postorder, postStart,
postStart + k - (inStart + 1));
// Becuase k is not the length, it it need to -(inStart+1) to get the length
root.right = buildTree(inorder, k + 1, inEnd, postorder, postStart + k- inStart, postEnd - 1);
// postStart+k-inStart = postStart+k-(inStart+1) +1

return root;
}