PREFIX - BINARY SEARCH TREE

Following algorithm is, to convert given prefix notation to Binary Search Tree.

If you find any discrepancies in this, feel free to post you comments.

Following is logic followed for algorightm.

1. Check if CHAR is OPERAND or OPERATOR.
2. If CHAR is OPERATOR, then
A) If this is first CHARACTER in ARRAY, insert into Array.
B) else
1) POP-UP Last Input from Array.
1) If it's left child is empty, then
1) assign this new node to left child
2) Insert POP-UP node back to array.
2) Else
1) assign this new node to Right child
2) Insert NEW Node in Array.

3. If CHAR is OPERAND, then
1) POP-UP Last Input from Array.
1) If it's left child is empty, then
1) assign this new node to left child
2) Insert POP-UP node back to array.
2) Else
1) assign this new node to Right child


Input : prefix notation string.
Output : Root of Tree.

typedeft struct BST_t
{
char info;
BST_t *left;
BST_t *right;
}BST;

BST * pretoBST ( char prefix[])
{
int i,k;
BST *tmp, *node;
char symbol;


for (i=k=0; (symbol = prefix[i])!='\0'; k++)
{
/* Create a new node */
tmp = CreateNode();
tmp->info = symbol;
tmp -> left = tmp -> right = NULL;

/* Check if SYMBOL is operand */

if (symbol == OPERAND )
{
node = ARR[--k];
if (node -> left == NULL)
{
node -> left = tmp;
ARR[k++] = node;
}
else
{
node -> right = tmp;
}

} /* End of If for SYMBOL == OPERAND*/
else
{
/* For the First Node */
if (k == 0)
{
node = ARR[--k];
if (node -> left == NULL)
{
node -> left = tmp;
ARR[k++] = node;
}
else
{
node -> right = tmp;
}
}
ARR [k++] = tmp;
} /* End of ELSE for SYMBOL == OPERAND*/

} /* End of For Loop */


/* Return Root of Tree */
return ARR[--k]
}