# Iterative solution in C with data structure "encapsulation"

• ``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/

struct node {
struct TreeNode *treenode;
struct node *next;
};

struct stack {
struct node *top;
int size;
};

void failIfNull(struct stack *stack){
if(!stack) exit(-1);
}

int isEmpty(struct stack *stack){
failIfNull(stack);
if(stack->size==0) return 1;
else return 0;
}

void newStack(struct stack **stack){
*stack=malloc(sizeof(struct stack));
(*stack)->size=0;
(*stack)->top=NULL;
}

void printStack(struct stack *stack){
struct node *node;
if(!stack){
printf("stack is null\n");
return;
}
printf("size %d.  vals: ",stack->size);
node=stack->top;
while(node){
if(!node->treenode){
printf("storing NULL treenode!\n");
}
printf("%d ",node->treenode->val);
node=node->next;
}
printf("\n");
}
struct TreeNode * pop(struct stack *stack){
struct node stackRes;
struct TreeNode *res;
failIfNull(stack);
if(isEmpty(stack))//implement a print error
exit(-1);
stackRes=*(stack->top);
stack->top=stack->top->next;
stack->size--;
res=stackRes.treenode;
return res;
}

void destroyStack(struct stack **stack){
failIfNull(*stack);
while(!isEmpty(*stack)){
pop(*stack);
}
free(*stack);
*stack=NULL;
}

void push(struct stack *stack, struct TreeNode *treenode){
failIfNull(stack);
struct node *newNode=malloc(sizeof(struct node));
newNode->next=stack->top;
newNode->treenode=treenode;
stack->top=newNode;
stack->size++;
printf("pushed %d\nnusize %d\n", treenode->val,stack->size);
}

struct dynamicA {
int maxSize;
int *array;
};

void initA(struct dynamicA **A, int maxSize){
*A=malloc(sizeof(struct dynamicA));
(*A)->array=malloc((maxSize)*sizeof(int));
(*A)->maxSize=maxSize;
}

/* void destroyA(struct dynamicA **A){ */
/*   if(!A)return; */
/*   if(*A && ( *A )->array) free(( *A )->array); */
/*   if(*A) free(*A); */
/*   *A=NULL; */
/* } */

void copyArray(int *fromA, int *toB, int n){
int i;
for(i=0;i<n;i++){
toB[i]=fromA[i];
}
}

void doubleA(struct dynamicA *A){
int *B;
B=malloc(2*A->maxSize*sizeof(int));
copyArray(A->array,B,A->maxSize);
free(A->array);
A->array=B;
A->maxSize=2*A->maxSize;
printf("nusize %d \n",A->maxSize);
}

int inRangeA(struct dynamicA *A,int i){
return i < A->maxSize;
}

void addItemA(struct dynamicA *A,int i,int val){
if(!inRangeA(A,i)){
doubleA(A);
}else{
A->array[i] = val;
}
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
struct dynamicA *A;
struct stack *stack;
newStack(&stack);
int indexA=0;
initA(&A,1);
struct TreeNode *node=root;
while(node){
push(stack,node);
node=node->left;
}
while(!isEmpty(stack)){
node=pop(stack);
if(node->right){
node=node->right;
while(node){