Level order traversal in spiral form |ZigZag Tree Traversal

So these 2 questions are quite popular in the interviews and are similar to one another.

(Asked in PayPal, Software Engineer 2, Round 2)

Level order traversal in spiral form - GeeksforGeeks

ZigZag Tree Traversal - GeeksforGeeks

Traversal in Spiral form output: 1,2,3,4,5,6,7

Zig Zag Traversal output: 1,3,2,7,6,5,4

To solve the above problem we will use 2 Stacks.

Stack1 will check the conditions and push the values in Stack2 Level wise (print left to right) Also Stack2 will check the conditions and push the values in Stack1 for Level wise (print right to left).

Here come the codes for both problems.

Traversal in Spiral form :

https://practice.geeksforgeeks.org/problems/level-order-traversal-in-spiral-form/1

class Node
{
    int data;
    Node left, right;
Node(int item)
    {
        data = item;
        left = right = null;
    }
}
*/
class Spiral
{
    //Function to return a list containing the level order 
    //traversal in spiral form. 
    ArrayList<Integer> findSpiral(Node root) 
    {
        return find(root);
    }
    
    public ArrayList<Integer> find(Node node){
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(node == null)
            return list;
        Stack<Node> stack1 = new Stack<Node>();
        Stack<Node> stack2 = new Stack<Node>();
        
        stack1.add(node);
        while(!stack1.isEmpty() || !stack2.isEmpty()){
        while(!stack1.isEmpty()){
            Node temp = stack1.peek();
            list.add(temp.data);
            stack1.pop();
            
            if(temp.right!=null)
                stack2.add(temp.right);
             if(temp.left!=null)
                stack2.add(temp.left);
        }
         while(!stack2.isEmpty()){
             Node temp = stack2.peek();
             list.add(temp.data);
             stack2.pop();
            
            if(temp.left!=null)
                stack1.add(temp.left);
             if(temp.right!=null)
                stack1.add(temp.right);
        }
        }
         return list;
    }
   
}

Zig Zag Tree Traversal :

https://leetcode.com/submissions/detail/484179312/

/**
 * Definition for a binary tree node.
 * public 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        return find(root);
    }
    
    public List<List<Integer>> find(TreeNode root){
        
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root==null)
            return result;
        
        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        
        stack1.add(root);
        
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            ArrayList<Integer> list = new ArrayList<Integer>();
            while(!stack1.isEmpty()){
                TreeNode temp = stack1.peek();
                list.add(temp.val);
                stack1.pop();
                
            if(temp.left!=null)
                stack2.add(temp.left);
            if(temp.right!=null)
                stack2.add(temp.right);
                
            }
            if(list.size()>0)
            result.add(list);
            list = new ArrayList<Integer>();
            
         while(!stack2.isEmpty()){
                TreeNode temp = stack2.peek();
                list.add(temp.val);
                stack2.pop();
                
            if(temp.right!=null)
                stack1.add(temp.right);
            if(temp.left!=null)
                stack1.add(temp.left);
                
            }
            if(list.size()>0)
             result.add(list);
        }
        return result;
        
    }
}

Here you can check the logic for both the problems are the same only the changes are made in how we are traversing the next level based on the problem statement.

Happy Coding!!