WAP to Traverse The Binary Tree In ZIG ZAG Order or Spiral Order

This Problem Can be Solved In Two Ways
1 By Recursion by Modifying Level Order Traversal
2.By Using two Stack


To Traverse the Tree in spiral order, nodes at different levels should be printed in alternating order. An additional Boolean variable alter is used to change printing order of levels. If ltr is 1 then printGivenLevel() prints nodes from left to right else from right to left. Value of ltr is flipped in each iteration to change the order.


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 (n) if Stack Space is considered else O(1)
Run Here https://ideone.com/cyPM5



Method 2 Using Recursion ( Modified Level Order Traversal)

Algorithm:

Function to print level order traversal of tree


printSpiralorder(tree)
bool alter= 0;
for d = 1 to height(tree)
printGivenOrder(tree, d, alter);
alter~= alter/*flip ltr*/
Function to print all nodes at a given level

printGivenOrder(tree, level)
if tree is NULL then return;
if level is 1, then
print(tree->data);
else if level greater than 1, then
if(alter)
printGivenOrder(tree->right, level-1, alter);
printGivenOrder(tree->left, level-1, alter);
else
printGivenOrder(tree->left, level-1, alter);
printGivenLevel(tree->right, level-1, alter);

Implementation:


#include
#include
#define bool int

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/*Function protoypes*/
void printGivenLevel(struct node* root, int level, int ltr);
int height(struct node* node);
struct node* newNode(int data);

/* Function to print spiral traversal of a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;

/*ltr -> Left to Right. If this variable is set,
then the given level is traverseed from left to right. */
bool Alter= 0;
for(i=1; i<=h; i++)
{
printGivenLevel(root, i, Alter);

/*Revert ltr to traverse next level in oppposite order*/
ltr = ~ltr;
}
}

/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level, int Alter)
{
if(root == NULL)
return;
if(level == 1)
printf("%d ", root->data);
else if (level > 1)
{
if(ltr)
{
printGivenLevel(root->left, level-1, Alter);
printGivenLevel(root->right, level-1, Alter);
}
else
{
printGivenLevel(root->right, level-1, Alter);
printGivenLevel(root->left, level-1, Alter);
}
}
}

/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lheight = height(node->left);
int rheight = height(node->right);

/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}

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

return(node);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(7);
root->left->right = newNode(6);
root->right->left = newNode(5);
root->right->right = newNode(4);
printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);

getchar();
return 0;
}


TC O(N^2)
SC O(1)
Run Here https://ideone.com/XGtsZ