Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Example:

Input:  
Output: 3 
        20 9 
        15 7 

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class BinaryTreeZigzagLevelOrderTraversal {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(3);
        tree.left = new TreeNode(9);
        tree.right = new TreeNode(20);
        tree.right.left = new TreeNode(15);
        tree.right.right = new TreeNode(7);
        List<List<Integer>> zig = zigzagLevelOrder(tree);
        System.out.println(Arrays.asList(zig));
    }

    // function to find the zigzag level order
    // traversal of binary tree
    static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null)
            return res;

        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();

        s1.push(root);
        boolean flag = false;
        List<Integer> x = new ArrayList<Integer>();

        // iterate till stack1 is not empty
        while (!s1.empty() || !s2.empty()) {
            if (!flag) {
                TreeNode temp = s1.pop();
                if (temp != null) {
                    x.add(temp.val);
                    // if direction from left to right
                    if (temp.left != null)
                        s2.push(temp.left);
                    if (temp.right != null)
                        s2.push(temp.right);
                }

                if (s1.empty()) {
                    // change the direction
                    flag = !flag;
                    // final result
                    res.add(x);
                    x = new ArrayList<Integer>();
                }
            } else {
                TreeNode temp = s2.pop();
                if (temp != null) {
                    x.add(temp.val);
                    if (temp.right != null)
                        s1.push(temp.right);
                    if (temp.left != null)
                        s1.push(temp.left);
                }
                if (s2.empty()) {
                    // change the direction
                    flag = !flag;
                    // final result
                    res.add(x);
                    x = new ArrayList<Integer>();
                }
            }
        }
        return res;
    }

}


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;
    }
}

  

C++

#include <bits/stdc++.h>
using namespace std;


//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};

//function to find the zigzag level order
//traversal of binary tree
vector<vector<int>> zigzagLevelOrder(TreeNode* root)
{
        vector<vector<int>> res;
        if(root==NULL)
               return res;

        stack<TreeNode *> s1,s2;
        s1.push(root);
        bool flag=false;
        vector<int> x;

        //iterate till stack1 is not empty
        while(!s1.empty())
         {
            TreeNode *temp=s1.top();
            s1.pop();
            if(temp)
            {
                x.push_back(temp->data);

                //if direction from left to right
                if(!flag)
                {
                    if(temp->left)
                           s2.push(temp->left);
                    if(temp->right)
                           s2.push(temp->right);
                }

                //if direction from right to left
                else
                {
                       
                    if(temp->right)
                           s2.push(temp->right);  
                      if(temp->left)
                           s2.push(temp->left);
                }
            }
           
            if(s1.empty())
            {
                //change the direction
                flag=!flag;

                //swap both the stacks
                swap(s1,s2);
                //push the current level into the
                //final result
                 res.push_back(x);
            x.clear();
            }
         }
        return res;
}
int main()
{
  TreeNode *root=new TreeNode(3);
  root->left=new TreeNode(9);
  root->right=new TreeNode(20);
  root->right->left=new TreeNode(15);
  root->right->right=new TreeNode(7);

  vector<vector<int>> zig=zigzagLevelOrder(root);
  for(int i=0;i<zig.size();i++)
    {
        for(int j=0;j<zig[i].size();j++)
            cout<<zig[i][j]<<" ";
        cout<<"\n";
    }
}