• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Level order traversal in Spiral form

December 21, 2014 by Dhaval Dave

Write a function to print spiral order traversal of a tree or Write function for Tree traversal in Spiral ZigZag form
For below tree, function should print 1, 2, 3, 7, 6, 5, 4.

           [1]
          /   \
       [2]     [3]
      /  \    /   \
    [4]  [5] [6]  [7]

1) Recursive

For odd height , we print tree from Reverse ie,for node (1), (4,5,6,7) , …
For Even height, we print tree from Front (2,3)
to do that in Level Order Traversal, we introduce variable flip and with that we can do that.

Algorithm

printSpiral(tree){
   bool flip = false;
   for H = 1 to height(tree){
      printGivenLevel(root, H, flip);
      flip =!  flip
   }
}
printGivenLevel(root, height, flip){
if root is NULL then return;
if heightis 1, then
    print(root->data);
else if height greater than 1, then
    if(flip)
        printGivenLevel(root->left, height-1, flip);
        printGivenLevel(root->right, height-1, flip);
    else
        printGivenLevel(root->right, height-1, flip);
        printGivenLevel(root->left, height-1, flip);
}


2) Iterative

Keep Two Stack S1, S2.
For Above example
Push 1 to S1.
Push 2,3 (R & L of 1) to S2.
Push 7,6 ( L & R of 3) to S1 and Push 5,4 (L & R of  2) to S1.
Continue this process

Algorithm

 

void printSpiral(struct node *root){
if root is NULL then return
stack<struct node*> S1
stack<struct node*> S2

S1.push(root)

While(S1 & S2 is not Empty){ //till both are not empty

  while(S1 not Empty){

  struct node *temp = S1.top()
  S1.pop()
  print temp->data
  //Push right and then left to S2//
  if(temp->right) S2.push(temp->right)
  if(temp->left) S2.push(temp->left) 

  }//while(s1 !Empty)

  while(S2 not Empty){

  struct node *temp = S2.top()
  S2.pop()
  print temp->data
  //Push left and then right to S1//
  if(temp->left) S1.push(temp->left)
  if(temp->right) S1.push(temp->right) 

  }//while(s2 !Empty)

  
}//While(S1,S2!Empty)

Code with Stack method

// C++ implementation of a O(n) time method for spiral order traversal
#include <iostream>
#include <stack>
using namespace std;

struct node
{
	int data;
	struct node *left, *right;
};
struct node* newNode(int data)
{
	struct node* node = new struct node;
	node->data = data;
	node->left = NULL;
	node->right = NULL;

	return(node);
}

void printSpiral(struct node *root)
{
	if (root == NULL) return;

	stack<struct node*> stack1;
	stack<struct node*> stack2;

	stack1.push(root);

	while (!stack1.empty() || !stack2.empty())
	{
		while (!stack1.empty())
		{
			struct node *temp = stack1.top();
			stack1.pop();
			cout << temp->data << " ";
			if (temp->right)
				stack2.push(temp->right);
			if (temp->left)
				stack2.push(temp->left);
		}
		while (!stack2.empty())
		{
			struct node *temp = stack2.top();
			stack2.pop();
			cout << temp->data << " ";
			if (temp->left)
				stack1.push(temp->left);
			if (temp->right)
				stack1.push(temp->right);
		}
	}
}

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);
	cout << "Spiral Order traversal of binary tree is \n";
	printSpiral(root);

	return 0;
}

See working code at http://ideone.com/4VM6us

Similar Articles

Filed Under: Amazon Interview Question, Interview Questions, Microsoft Interview Questions, problem Tagged With: Binary Tree, Stack, tree

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Regular Expression Matching

Find the kth number with prime factors 3, 5 and 7

Find next greater number with same set of digits

Find the smallest window in a string containing all characters of another string

CodeChef Code SGARDEN

Client Server C program

Memory Efficient LinkedList

Wrong Directions given find minimum moves so that he can reach to the destination

Linked List V/S Binary Search Tree

flattens 2 D linked list to a single sorted link list

Find loop in Singly linked list

The greedy coins game Dynamic Programming

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

Spanning Tree

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

SAP Off Campus Hiring_ March 2015 Verbal Skills

How strtok() Works

Length of the longest substring without repeating characters

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

LeetCode: Binary Tree Maximum Path Sum

Connect n ropes with minimum cost

CodeChef’ RRCOPY

LeetCode: Container With Most Water

Find min element in Sorted Rotated Array (Without Duplicates)

simple sql injection

Printing intermediate Integers between one element & next element of array

K’th Largest Element in BST when modification to BST is not allowed

Copyright © 2025 · Genesis Framework · WordPress · Log in