Given a binary tree, print the zigzag level order traversal of its node values. (ie, from left to right, then right to left for the next level and alternate between).
Table of Contents
Example
consider the binary tree given below
Below is the zigzag level order traversal of the above binary tree
Types of Solution for Binary Tree zigzag level order Traversal
- using Breadth First search and two stacks
- using Depth First search and Map
BFS and two stacks
Approach for Binary Tree zigzag level order Traversal
We perform BFS on the tree and use two stacks namely current and next. current stores all the nodes in the current level in an order (left to right or right to left). next stores all the nodes of the next level in an order opposite to current. After processing all the elements of the current level, when the current becomes empty, we move the nodes stored in next into current and move on to the next level. Now, next-level nodes are again stored in next. This process goes on till the current and next stacks are not empty.
Algorithm
- Create two stacks current and next.
- Create a boolean variable leftOrRight, that is used to switch from left-to-right mode to right-to-left mode.
- insert root into current and begin BFS traversal.
- BFS traversal :
- Pop a node from the current stack, print its value.
- check the mode using leftOrRight.
- if mode is left-to-right(i.e. leftOrRight = true), then insert children(left before right) of current node into next stack.
- if mode is right-to-left(i.e. leftOrRight = false), then insert children(right before left) of current node into next stack.
- Once the current stack becomes empty after processing all the nodes of the current level, move onto the next level. Empty all the nodes of next into the current.
- From now on, all the children of nodes on the current will be stored in next.
- Perform steps 4.1-4.6 until current and next stacks are not empty.
Implementation
C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// blueprint of the tree node
class Node
{
public :
int data;
Node *left, *right, *next;
Node(int key)
{
data = key;
left = right = next = NULL;
}
};
/* function that performs zigzag Traversal
in similar manner to BFS */
void zigzagTraversal(Node *root)
{
/*check if the tree is empty*/
if(root == NULL)
return;
/*create two stacks*/
/*current stores the current level order Traversal,
next stores the next level order traversal */
stack<Node*> current;
stack<Node*> next;
/*start with root*/
current.push(root);
/*leftOrRight is to check whether to traverse from right or left*/
/*Change it after every traversing every level*/
bool leftOrRight = true;
while(!current.empty())
{
Node *curr = current.top();
current.pop();
if(curr != NULL)
{
cout<<curr->data<<" ";
/* if next level has to be traversed left to right*/
if(leftOrRight)
{
if(curr->left)
next.push(curr->left);
if(curr->right)
next.push(curr->right);
}
/* if next level has to be traversed right to left*/
else
{
if(curr->right)
next.push(curr->right);
if(curr->left)
next.push(curr->left);
}
/*if the current level has been completely
traversed and we have to move on to next level*/
if(current.empty())
{
swap(current,next);
leftOrRight = !leftOrRight;
}
}
}
}
// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
if(root == NULL)
return;
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
int main()
{
/*create the Binary Tree*/
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->right = new Node(6);
root->left->left->left = new Node(7);
root->right->right->right = new Node(8);
zigzagTraversal(root);
return 0;
}1 3 2 4 5 6 8 7
Java Program
import java.util.*;
import java.io.*;
class tutorialCup
{
// blueprint of the tree node
static class Node
{
int data;
Node left, right, next;
Node(int key)
{
data = key;
left = right = next = null;
}
}
/* function that performs zigzag Traversal
in similar manner to BFS */
static void zigzagTraversal(Node root)
{
/*check if the tree is empty*/
if(root == null)
return;
/*create two stacks*/
/*current stores the current level order Traversal,
next stores the next level order traversal */
Stack <Node> current = new Stack<>();
Stack <Node> next = new Stack<>();
/*start with root*/
current.push(root);
/*leftOrRight is to check whether to traverse from right or left*/
/*Change it after every traversing every level*/
boolean leftOrRight = true;
while(!current.isEmpty())
{
Node curr = current.pop();
if(curr != null)
{
System.out.print(curr.data+" ");
/* if next level has to be traversed left to right*/
if(leftOrRight)
{
if(curr.left != null)
next.push(curr.left);
if(curr.right != null)
next.push(curr.right);
}
/* if next level has to be traversed right to left*/
else
{
if(curr.right != null)
next.push(curr.right);
if(curr.left != null)
next.push(curr.left);
}
/*if the current level has been completely
traversed and we have to move on to next level*/
if(current.isEmpty())
{
Stack <Node> temp = current;
current = next;
next = temp;
leftOrRight = !leftOrRight;
}
}
}
}
// function to simply perform inorder traversal of the tree
static void inorder(Node root)
{
if(root == null)
return;
inorder(root.left);
System.out.print(root.data+" ");
inorder(root.right);
}
public static void main (String[] args)
{
/*create the Binary Tree*/
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(6);
root.left.left.left = new Node(7);
root.right.right.right = new Node(8);
zigzagTraversal(root);
}
}1 3 2 4 5 6 8 7
Complexity Analysis for Binary Tree zigzag level order Traversal
- Time Complexity : T(n) = O(n)
- Space Complexity : T(n) = O(2n) = O(n), two stacks are used.
DFS and Map
Approach for Binary Tree zigzag level order Traversal
We use a Hashmap data structure. This Hashmap maps the level(an integer value) of the tree against a dynamic array (containing all the nodes of that particular level). On performing an inorder traversal using the map, we obtain the required mapping. It should be ensured that consecutive levels are printed in opposite orders.
The mapping obtained is as follows:
(level -> dynamic array {containing nodes at that level})
Algorithm
- Create a Hashmap variable memo.
- Perform an inorder traversal using a memo and keep track of the level of each node of the tree.
- If a particular level (as key-value) is not present in the map, insert that level (as key) into the map and map it to an empty dynamic array (mapped value).
- Insert the nodes encountered during traversal into a vector(the dynamic array corresponding to the level of that node).
- After traversal is complete, print adjacent levels each in the opposite order to the order of printing of the previous level. (each level is a dynamic array containing tree nodes)
Implementation
C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// blueprint of the tree node
class Node
{
public :
int data;
Node *left, *right, *next;
Node(int key)
{
data = key;
left = right = next = NULL;
}
};
/* this function performs inorder traversal stores the nodes in various levels */
/* Mapping : int->vector, where int is the level number
and vector stores all the nodes at a particular 'level'*/
void inorderStore(Node* root,unordered_map<int,vector <int>> &memo,int level)
{
if(root == NULL)
return;
inorderStore(root->left,memo,level+1);
/* if a particular level has not been visited so far*/
if(memo.find(level) == memo.end())
{
/* add the level and vector corresponding to it into the map*/
vector <int> arr = {};
memo.insert({level,arr});
}
/* add nodes into their respective levels*/
memo[level].push_back(root->data);
inorderStore(root->right,memo,level+1);
}
/* function that performs zigzag Traversal
in similar manner to BFS */
void zigzagTraversal(Node *root)
{
/* create a map */
unordered_map <int,vector<int> > memo;
int level = 1;
/* store values into the map(level-wise) using inorder traversal */
inorderStore(root,memo,level);
/* traverse the map and print nodes by level */
for(int i=1;i<=memo.size();i++)
{
if(i%2 == 1)
{
for(int j = 0;j<memo[i].size();j++)
cout<<memo[i][j]<<" ";
}
/* alternate levels are to be printed in reverse order to produce zigzag traversal */
else
{
for(int j = memo[i].size()-1;j >= 0;j--)
cout<<memo[i][j]<<" ";
}
}
}
// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
if(root == NULL)
return;
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
int main()
{
/*create the Binary Tree*/
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->right = new Node(6);
root->left->left->left = new Node(7);
root->right->right->right = new Node(8);
zigzagTraversal(root);
return 0;
}1 3 2 4 5 6 8 7
Java Program
import java.util.*;
import java.io.*;
class tutorialCup
{
// blueprint of the tree node
static class Node
{
int data;
Node left, right, next;
Node(int key)
{
data = key;
left = right = next = null;
}
}
/* this function performs inorder traversal stores the nodes in various levels */
/* Mapping : int->vector, where int is the level number
and vector stores all the nodes at a particular 'level'*/
static void inorderStore(Node root,HashMap<Integer,ArrayList<Integer>> memo,int level)
{
if(root == null)
return;
inorderStore(root.left,memo,level+1);
/* if a particular level has not been visited so far*/
if(!memo.containsKey(level))
{
/* add the level and vector corresponding to it into the map*/
ArrayList <Integer> arr = new ArrayList<>();
memo.put(level,arr);
}
/* add nodes into their respective levels*/
memo.get(level).add(root.data);
inorderStore(root.right,memo,level+1);
}
/* function that performs zigzag Traversal
in similar manner to BFS */
static void zigzagTraversal(Node root)
{
/* create a map */
HashMap <Integer,ArrayList<Integer>> memo = new HashMap<>();
int level = 1;
/* store values into the map(level-wise) using inorder traversal */
inorderStore(root,memo,level);
/* traverse the map and print nodes by level */
for(int i=1;i<=memo.size();i++)
{
if(i%2 == 1)
{
for(int j=0;j<memo.get(i).size();j++)
System.out.print(memo.get(i).get(j)+" ");
}
/* alternate levels are to be printed in reverse order to produce zigzag traversal */
else
{
for(int j=memo.get(i).size()-1;j >= 0;j--)
System.out.print(memo.get(i).get(j)+" ");
}
}
}
// function to simply perform inorder traversal of the tree
static void inorder(Node root)
{
if(root == null)
return;
inorder(root.left);
System.out.print(root.data+" ");
inorder(root.right);
}
public static void main (String[] args)
{
/*create the Binary Tree*/
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(6);
root.left.left.left = new Node(7);
root.right.right.right = new Node(8);
zigzagTraversal(root);
}
}1 3 2 4 5 6 8 7
Complexity Analysis for Binary Tree zigzag level order Traversal
- Time Complexity : T(n) = O(nlogn), inorder traversal takes O(n) time. However, printing nodes at each level will take O(nlogn) in the worst case (in case of a full binary tree).
- Space Complexity : A(n) = O(n), for using map data structure.