# C: Stack with binary search trees

gruba

## Homework Statement

Create a linear stack with N binary search trees (data of a tree node is an integer). Read N trees, push them on the stack. Then, empty the stack and store trees in the new array and print the content of the stack.

2. The attempt at a solution
The following code gives unexpected output (stack content is not printed correctly - look at the printing stack loop at the line $\sim$ 215):
Code:
#include<stdio.h>
#include<stdlib.h>
#define N 2

typedef struct
{
int num;
}TREE_INFO;

typedef struct tree_node
{
TREE_INFO treeInfo;
struct tree_node *left,*right;
}TREE_NODE;

typedef struct stack
{
TREE_NODE arr[N];
int tos;
}STACK;

int isFull(STACK *s)
{
return s->tos == N-1;
}

int isEmpty(STACK *s)
{
return s->tos ==-1;
}

int push(STACK *s,TREE_NODE *stackInfo)
{
if(isFull(s))
return0;
s->arr[++s->tos]=*stackInfo;
return1;
}

int pop(STACK *s,TREE_NODE *stackInfo)
{
if(isEmpty(s))
return0;
*stackInfo=s->arr[s->tos--];
return1;
}

TREE_NODE* emptyTheStack(STACK *s)
{
if(isEmpty(s))
return0;
int i=0;
TREE_NODE *arr=(TREE_NODE*)malloc(((s->tos+1)*sizeof(TREE_NODE))*N *1000);
while(!isEmpty(s))
arr[i++]=s->arr[s->tos--];
return arr;
}

{
do
{
printf("Enter positive integer: ");
scanf("%d",&treeInfo->num);
}
while(treeInfo->num <0);
}

TREE_NODE* searchTree(TREE_NODE *root,int num)
{
if(root ==0)
return0;
elseif(num == root->treeInfo.num)
return root;
elseif(num <= root->treeInfo.num)
return searchTree(root->left,num);
elsereturn searchTree(root->right,num);
}

TREE_NODE* formNode(TREE_INFO *treeInfo)
{
TREE_NODE*newNode=(TREE_NODE*)malloc(sizeof(TREE_NODE));
newNode->left=newNode->right=0;
newNode->treeInfo=*treeInfo;
return newNode;
}

{
if(root ==0)
return formNode(treeInfo);
if(treeInfo->num <= root->treeInfo.num)
return root;
}

void deleteTree(TREE_NODE *root)
{
if(root !=0)
{
deleteTree(root->left);
deleteTree(root->right);
free(root);
}
}

void printTreeInorder(TREE_NODE *root)
{
if(root !=0)
{
printTreeInorder(root->left);
printf("%d ",root->treeInfo.num);
printTreeInorder(root->right);
}
}

int main()
{
int i;
TREE_INFO treeInfo;
char option;
TREE_NODE *srch,*root,*arr;
STACK st;
st.tos=-1;
i=1;
root=0;
printf("Adding N trees on the stack: \n");

while(i<=N)
{
do
{
fflush(stdin);
printf("\nEnter option: ");
scanf("%c",&option);
if(option =='A')
{
fflush(stdin);
printf("Enter data about %d. tree: \n",i);
srch=searchTree(root,treeInfo.num);
if(srch)
srch->treeInfo=treeInfo;
else
}
elseif(option =='P')
{
printTreeInorder(root);
}
elseif(option !='0')
printf("Unknown option.\n");
}
while(option !='0');

if(push(&st,root))
printf("%d. tree is pushed on the stack.\n",i);

if(isFull(&st))
printf("Stack is full.\n");

root=0;
srch=0;
i++;
}

arr=emptyTheStack(&st);
i=1;
printf("Printing stack: \n");
while(i<=N)
{
printTreeInorder(arr);
i++;
}

if(isEmpty(&st))
printf("Stack is empty.\n");

free(arr);

return0;
}

Example program:

Code:
Enter option: A
Enter option: A
Enter option: A
Enter option: P //print a tree
Data about 1. tree:8 10//note: inorder traversal without duplicate values
Enter option:0
1. tree is pushed on the stack.

Enter option: A
Enter option: A
Enter option: P
Enter option:0
2. tree is pushed on the stack.

Stack is full.

Print stack:

6 9
8 10

For the same input, I am getting the following output:
Code:
Print stack:

6 9
6 9

This means that the last input tree is printed N times.
Could someone point out how to resolve this error?

Thanks for replies.