Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach - Using Two Stacks
2.1.
Time and Space Complexity
3.
Frequently Asked Questions
3.1.
What is a Binary Tree?
3.2.
What is the ZigZag traversal of Binary Tree?
3.3.
What is the best case time complexity for the ZigZag traversal of the Binary Tree?
3.4.
What are the different possible Traversals for Binary Trees?
4.
Conclusion
Last Updated: Mar 27, 2024

ZigZag Traversal of Binary Tree

Author Raksha Jain
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Today, let's learn about a famous and commonly asked Interview Problem, i.e., the ZigZag Traversal of a Binary Tree.

So, Binary Tree is a generic tree with only two children, i.e., left and right. And ZigZag Traversal of a Binary Tree here means that we need to print the nodes in the given tree in a zigzag manner, i.e., from left to right for the first level, then right to left for the next level and so on, following alternate directions for alternate levels.   

 

Problem Statement: Given the root of the binary tree, we need to return the zigzag level order traversal of its nodes' values.

Example: 

Tree

 

So, here we would first print the root (3) and then traverse right to left and print [20,9] and then finally traverse left to right printing [15,7], completing the ZigZag traversal of Binary Tree.

 

Let's get started and learn various approaches to solving this problem. 

Recommended: Do try the Problem by yourself first before moving on to the solution.

Approach - Using Two Stacks

We could achieve ZigZag traversal of Binary Tree by having 2 stacks(Stack - A LIFO data structure) for alternate (left to right) and (right to the left) traversal and then print the nodes alongside.

 

So, 

Step1: We create 2 stacks of type TreeNode. Initially, stack1 stores the root, and stack2 is empty. 

We work till both the stacks are not empty.

We then enter inside the loop where we perform the following steps:

  • While (Stack1’s size() > 0)
    • The popped node’s Right Child (Rc) is entered in stack2 and printed if it exists.
    • The popped node’s Left Child (Lc) is entered in stack2 and printed if it exists.
  • While (Stack2’s size() > 0)
    • The popped node’s Left Child (Lc) is entered in stack1 and printed if it exists.
    • The popped node’s Right Child (Rc)is entered in stack1 and printed if they exist. 

 

Let us do a dry run on this tree for a better understanding:

Tree

 

Stack1 - [8] Stack2 - [ ]. Also,  Root ie 8 is printed. 

Stack
Stack

 

We enter the while loop:

  1. So,  8 is popped from Stack1 and its Rc(10) and Lc(3) are added in Stack2. 

Stack1 =[] Stack2 = [3, 10] and 10 3 are printed.

Stack
Stack

2.  So,  3 is popped from Stack2, and its Lc(1) and Rc(6) are added in Stack1. 

Stack1 =[6,1] Stack2 = [10] and 1 6 are printed.

Stack
Stack

3.  10 is popped from Stack2 and its Rc(14) is added in Stack1. (Lc of 10 does not exist).

Stack1 =[14, 6,1] Stack2 = [ ] and 14 is printed.

Stack
Stack

4.  Similarly, 14 is popped from Stack1, and its Rc(13) is added in Stack2. (Lc of 14 does not exist).

Stack1 =[6,1] Stack2 = [13] and 13 is printed.

Stack
Stack

 

5.  6 is popped from Stack1 and its Rc(7) and Lc(4) are added in Stack2. 

Stack1 =[1] Stack2 = [4,7,13] and 7, 4 are printed.

Stack
Stack

 

6.  1 is popped from Stack1. Lc and Rc of 1 do not exist.

Stack1 =[] Stack2 = [4,7,13]

Stack
Stack

7.  4 is popped from Stack2. Lc and Rc of 4 do not exist.

Stack1 =[] Stack2 = [7,13]

Stack
Stack

8.  7 is popped from Stack1. Lc and Rc of 7 do not exist.

Stack1 =[] Stack2 = [13]

Stack
Stack

 

9.  13 is popped from Stack1. Lc and Rc of 13 do not exist.

Stack1 =[] Stack2 = []

Since both the stacks are empty, the loop ends. 

Stack
Stack

 

Stack

Implementation-

Let’s have a look at its implementation in Java -

import java.util.*;
import java.lang.*;
import java.io.*;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
 
class Solution {
    public static void zigzagLevelOrder(TreeNode root) {
        
        System.out.println("ZigZag traversal of Binary Tree: ");
        
        // Creating 2 stacks to store alternate levels
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        
        // When a node is added, it is printed too.
        stack1.push(root);
        System.out.println(root.val);
        while (stack1.size() > 0 || stack2.size() > 0){
            
            //Stack1's elements are removed and its children are added into stack2 
            //in form - Rc Lc(Right child and Left child)
            while (stack1.size() > 0){
                TreeNode currNode = stack1.pop();
                if (currNode.right != null){
                    System.out.print(currNode.right.val + " ");
                    stack2.push(currNode.right);
                }
            
                if (currNode.left != null){
                    System.out.print(currNode.left.val + " ");
                    stack2.push(currNode.left);
                }
                System.out.println();
            }
            
            //Stack2's elements are removed and its children are added into stack1 
            //in form Lc Rc(Left cild and Right child)
            while (stack2.size() > 0){
                TreeNode currNode = stack2.pop();
                if (currNode.left != null){
                    System.out.print(currNode.left.val + " ");
                    stack1.push(currNode.left);
                }
            
                if (currNode.right != null){
                    System.out.print(currNode.right.val + " ");
                    stack1.push(currNode.right);
                }
                System.out.println();
            }
        }
    }
 
    
    public static void main (String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("Form a tree: ");
        TreeNode root = new TreeNode(s.nextInt());
        root.left = new TreeNode(s.nextInt());
        root.right = new TreeNode(s.nextInt());
        root.right.left = new TreeNode(s.nextInt());
        root.right.right = new TreeNode(s.nextInt());
        
        zigzagLevelOrder(root);
    }
}

 

Output:

Form a tree: 3 9 20 15 7 

ZigZag traversal of Binary Tree: 

3

20 9 

15 7 

 

Time and Space Complexity

Time Complexity: O(n) as we are traversing all the nodes of the Binary tree in ZigZag traversal of Binary Tree at least once.

 

Space Complexity: O(n) as extra space for storing the nodes of alternate levels in the stack has been used.

Where n is the number of nodes in a Binary Tree.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a Binary Tree?

A generic tree with at most two child nodes for each parent node is known as a Binary Tree. An empty tree is also considered a valid Binary Tree.

What is the ZigZag traversal of Binary Tree?

ZigZag Traversal of a Binary Tree means that we need to print the nodes in the given tree in a zigzag manner, i.e., from left to right, then right to left for next level, and so on, following alternate directions for alternate levels.  

What is the best case time complexity for the ZigZag traversal of the Binary Tree?

The best-case time complexity for ZigZag Traversal of a Binary Tree is O(1), i.e. when only a single or no node is present in the Binary Tree. 

What are the different possible Traversals for Binary Trees?

The different possible traversals of Binary Tree are level-order traversal, Diagonal traversal, etc.

 

Conclusion

In this blog, we learned various approaches for the ZigZag traversal of Binary Trees.

 

  • ZigZag Traversal of a Binary Tree means that we need to print the nodes in the given tree in a zigzag manner, i.e., from left to right, then right to left for the next level, and so on, following alternate directions for alternate levels.
  • The minimum space complexity required is O(n) where n = number of nodes in a Binary Tree as we need to store all the nodes of a Binary Tree in any used data structure.
  • The different possible traversals of Binary Tree are level-order traversal, Diagonal traversal, etc.

Recommended Reading:

Recommended problems -

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Previous article
Level order traversal with direction change after every two levels
Next article
Boundary Traversal Of Binary Tree (Recursive and Iterative)
Live masterclass