Spiral Order traversal of Tree in C
Spiral Order Traversal of Binary Tree in C
Given a Tree and we need to print the spiral order traversal of the given tree. By spiral Order Traversal We mean that alternate levels should be printed in alternate order .
Example – Level 0 to be printed left to right
Level 1 from right to left, and so on.
Spiral Order Traversal of Binary Tree In C
Algorithm :
- Create a Boolean variable ltr which 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.
- Function to print level order traversal :
- printSpiral(tree) set ltr to 0;
- Run a loop from 0 to height -1
- printGivenLevel(tree, d, ltr);
- ltr ~= ltr /*flip ltr*/
- To print the nodes is :if tree is NULL then return;
- if level is 1, then print(tree->data);
- else if level greater than 1, then
- if(ltr) printGivenLevel(tree->left, level-1, ltr) and printGivenLevel(tree->right, level-1, ltr);
- else printGivenLevel(tree->right, level-1, ltr) and printGivenLevel(tree->left, level-1, ltr);
Code in C for Spiral Order Traversal
Run
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
void printGivenLevel (struct node *root, int level, int ltr);
int height (struct node *node);
struct node *newNode (int data);
void printSpiral (struct node *root)
{
int h = height (root);
int i;
bool ltr = false;
for (i = 1; i <= h; i++)
{
printGivenLevel (root, i, ltr);
ltr = !ltr;
}
}
void printGivenLevel (struct node *root, int level, int ltr)
{
if (root == NULL)
return;
if (level == 1)
printf ("%d ", root->data);
else if (level > 1)
{
if (ltr)
{
printGivenLevel (root->left, level - 1, ltr);
printGivenLevel (root->right, level - 1, ltr);
}
else
{
printGivenLevel (root->right, level - 1, ltr);
printGivenLevel (root->left, level - 1, ltr);
}
}
}
int height (struct node *node)
{
if (node == NULL)
return 0;
else
{
int lheight = height (node->left);
int rheight = height (node->right);
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
}
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);
}
int main ()
{
struct node *root = newNode (10);
root->left = newNode (20);
root->right = newNode (30);
root->left->left = newNode (40);
root->left->right = newNode (50);
root->right->left = newNode (60);
root->right->right = newNode (70);
printf ("Spiral Order traversal of binary tree is \n");
printSpiral (root);
return 0;
}
Output
Spiral Order traversal of binary tree is 10 20 30 70 60 50 40
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Login/Signup to comment