Generate a binary tree from its inorder and preorder sequence

preIn.cpp

// inorderMap maps from value to its inorder index (no dup value in tree)
// pre changes in each recursive call, pre[0] is alway the next root value
// l is the left index of the inorder range we investigate in current call
// r is the right index of the inorder range
Node* buildPreIn(map<int, int> inorderMap, int pre[], int l, int r) {
    // terminate condition l < r
    // when l==r, we still need to proceed and create the leaf node
    if (l > r) return NULL;

    int curValue = pre[0];
    int inorderIdx = inorderMap[curValue];
    Node* cur = new Node(curValue);

    // in preorder, the left child is visited right after the root
    // we pass pre+1, so that in the next call pre[0] is the next root value
    // The inorder range is changed from [l, r] to [l, inorderIdx-1]
    cur->left = buildPreIn(inorderMap, pre+1, l, inorderIdx-1);

    // in preoder, the right child is visited after all the left subtree
    // we get the num of node in the left subtree from the inorder index
    // (inorderIdx-l+1) is all the nodes in the left subtree, we add it to pre
    // The inorder range is changed from [l, r] to [inorderIdx+1, r]
    cur->right = buildPreIn(inorderMap, pre+inorderIdx-l+1, inorderIdx+1, r);

    return cur;
}