## using traversal pairs to build a tree

I'm working on a project that needs to read preorder and inorder traversals, and print out the three orders (pre, in, post)

My tree is not correct at all, appreciate anyone who can help me on this. This tree is not a binary search one, so no need to compare the value.

My algorithm: preorder[0] is the root
preorder[1] is the root of the subtree
always get the nextkey from preorder
compare the indexes found in inorder.
for instance, if current index is less the previous
keyindex, it's in the left subtree

//instance: inorderArray
6 15 9 4 13 11
| | |
left root right

//instance: preorderArray
4 6 9 15 11 13

37 is inorderArray[2], it must be inserted right under 29 (inorderArray[1])

I don't know how to make T2 and T3 work correctly in this code. I need help!

//preArray: elements in preorder
//inArray: elements in inorder
//size: number of elements

void createTree(treeNode* &Rt, int preArray[], int inArray[], int size)
{
treeNode *T1, *T2, *T3; //T1 is new node to be inserted
//T2, T3 used to find the postion and linking nodes

int k; //loop counter
int rootIndex;
int keyIndex;
int keyIndexArray[size];
rootIndex = findRoot(inArray, size, preArray[0]);
//keyIndex = findRoot(inArray, size, preArray[0]);
keyIndexArray[0] = rootIndex;
cout << "keyIndexArray[0]: " << keyIndexArray[0] << endl;

//create root
Rt = new treeNode;
Rt->data = preArray[0];
cout << "Rt is: " << Rt->data << endl;
Rt->lchild_ = NULL;
Rt->rchild_ = NULL;
T2 = Rt;
T3 = Rt;

//traverse the preorderArray, and insert
for ( k = 1; k < size; k++)
{
keyIndex = findRoot(inArray, size, preArray[k]);

keyIndexArray[k] = keyIndex;
cout << "keyIndexArray[" << k <<"]: " << keyIndexArray[k] << endl;
cout << "keyIndex is: " << keyIndex << endl;
T1 = new treeNode;
T1->data = preArray[k];
cout << "the next key is: " << T1->data << endl;
T1->lchild_ = NULL;
T1->rchild_ = NULL;

while (T2 != NULL) //T2 is used to find the correct positon
{
T3 = T2;
if (keyIndexArray[k] < keyIndexArray[k-1])

T2 = T2->lchild_;

else
T2 = T2->rchild_;

}

//T3 is used for linking the nodes together, I don't know how
to fix this part. The condition for if is not correct. I can't think of
the way to set it right.

if (keyIndexArray[k] < keyIndexArray[k-1] && keyIndexArray[k] < rootIndex)

T3->lchild_ = T1;
else
T3->rchild_ = T1;

T2 = Rt;
}
}
//
//
void traverse(treeNode *p)
{
if ( p != NULL )
{
traverse(p->lchild_);
cout << p->data << " ";
traverse(p->rchild_);
}

}

Thanks for reading and help.