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]
}

BINARY SEARCH TREE :- Level Order Traversal

Following is an algorithm or psuedocode for Traversing Binary Search Tree in Level Order.

If anyone thinks, there is any mistake in given algorithm please feel free to post your comments I will check and update this accordingly.

Following is logic:
1. Start From Root.
2. Store Left and Right Child in Array.
3. Takeout last element from Array and Process and Repeat Step 2.
4. Continue this process until Array completes.


typedef structure BST_t
{
int info;
BST_t *left;
BST_t *right;
}BST;

void BSTLevelOrdTraversal (BST *root)
{

int i = 0,index;
BST ARR[100];
BST *tmp;

index =0;
ARR[i] = root;
do
{
tmp = ARR[index];
printf ("%d", tmp -> info);

/* Store Left Child in Array */

if (tmp -> left != NULL)
ARR[++i] = tmp->left;

/* Store Right Child in Array */
if (tmp -> right != NULL)
ARR[++i] = tmp->right;

index ++;
} while ( i >= index);

}