WAP to Convert Zig Zag level order Traversal of Tree to Doubly Linked List

Method 1 using 2-Stack--Need Modification RunTime Error But Logic is 100% Correct

#include
#include

/* Structure for Tree */
struct node
{
struct node* left;
struct node* right;
int data;
};

/* structure of a stack node */
struct sNode
{
struct node *t;
struct sNode *next;
};

/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct node* newtNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}


/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct node *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));

if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_tNode->t = t;

/* link the old list off the new tNode */
new_tNode->next = (*top_ref);

/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}

/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}

/* Function to pop an item from stack*/
struct node *pop(struct sNode** top_ref)
{
struct node *res;
struct sNode *top;

/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}

void Insert(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* since we are adding at the begining,
prev is always NULL */
new_node->left= NULL;

/* link the old list off the new node */
new_node->right= (*head_ref);

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->left= new_node ;

/* move the head to point to the new node */
(*head_ref) = new_node;
}

void Spiral(struct node* root)
{
struct node *head;//for DLL
struct sNode *node1;
struct sNode *node2;
struct node *temp;


if(root == NULL)
return;

push(&node1,root);


while(!isEmpty(node1) && !isEmpty(node2))
{

while(!isEmpty(node1))
{
temp = pop(&node1);
Insert(&head,temp->data);
push(&node2,temp->right);
push(&node2,temp->left);
}
//temp=NULL;

while(!isEmpty(node2))
{
temp = pop(&node2);
Insert(&head,temp->data);
push(&node1,temp -> left);
push(&node1,temp -> right);
}

}

}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}

/* Utility function to print a linked list */
void printList(struct node* head)
{
while(head!=NULL)
{
printf("%d ",head->data);
head=head->right;
}
printf("\n");
}

/* Driver function to test above functions */
int main()
{
struct node *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
root->right->left = newtNode(6);
root->right->right = newtNode(7);

Spiral(root);
printList(root);

getchar();
}

TC O(n)
Sc (2n) if Stack Space is considered else O(1)
Run Here https://ideone.com/cyPM5

Method 2 Using Recursion(Bottom Up Tree Traversal)


#include
#include

struct node
{
struct node *left;
struct node *right;
int data;

};

struct node *rslt;//Global structure pointer..it point to head of doubly linked list


int height(struct node* head)
{

if(head==NULL)
return 0;

if(head->left==NULL && head->right==NULL)
return 0;

int lh=height(head->left);
int rh=height(head->right);

return lh>rh?(lh+1):(rh+1);

}

struct node* appnd(struct node *a,struct node *b)
{
if(a==NULL)return b;
if(b==NULL)return a;

struct node* result=a;
while(a->left!=NULL)
a=a->left;

a->left=b;
b->right=a;

b->left=NULL;

return result;

}

void printGivenLevel(struct node* head,int level,int ltr)
{
if(head==NULL)
return;

if(level==0)
{
appnd(rslt, head);
rslt = head;
}

if(level>0)
{

if(ltr)
{
printGivenLevel(head->left,level-1,ltr);
printGivenLevel(head->right,level-1,ltr);
}
else
{
printGivenLevel(head->right,level-1,ltr);
printGivenLevel(head->left,level-1,ltr);

}
}

}

void printGivenOrder(struct node* head)
{

int i=0;
int ltr=0;

for(i=height(head); i >= 0; i--)
{

printGivenLevel(head,i,ltr);
ltr=~ltr;
}

}

struct node* NewNode(int data)
{
struct node* tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=data;
tmp->left=NULL;
tmp->right=NULL;
return tmp;

}

void printList(struct node* node)
{
struct node* current=node;
while(current)
{
printf("%d ----> ",current->data);
current=current->right;
}


}

int main()
{
struct node* start=NULL;

start=NewNode(1);
start->left=NewNode(2);
start->right=NewNode(3);
start->left->left=NewNode(4);
start->left->right=NewNode(5);
start->right->left=NewNode(6);
start->right->right=NewNode(7);

printGivenOrder(start);

printList(rslt);

return 0;

}
TC O(n^2)....need Modification..??
Sc O(1)
Run Here https://ideone.com/y9Ssb