ZigZag Tree Traversa

//Method 1: Time complexity O(n) but two iteration
/*Logic:
we will travere the tree levelwise and we will switch the flag levelwise,while traversing  nodes of a level,we
wiil push those nodes in a temporaray vector and then print those vectors in alternate direction,one time normal
and next ime reversed
*/
class Solution{
    public:
    //Function to store the zig zag order traversal of tree in a list.
    vector <int> zigZagTraversal(Node* root)
    {
        if(root == NULL){return {  } ; }

        vector<int > ans ;
        queue<Node*> q ;
        q.push(root) ;
        bool flag = false ;

        while(!q.empty()){
            int size = q.size() ;
            vector<int> level ;
            for(int i=0 ; i < size ; i++){
                Node* node = q.front() ;
                q.pop() ;
                level.push_back(node->data) ;

                if(node->left != NULL) {q.push(node->left) ;}
                if(node->right != NULL) {q.push(node->right) ;}

            }
            flag = !flag ;
            if(flag == false){
                reverse(level.begin() , level.end()) ;
            }
            for(int i = 0 ; i < level.size() ; i++){
              ans.push_back(level[i]) ;
            }

        }
        return ans ;
    }
};
//Method 2:- Single pass O(n)
/*
Logic:
We will use deque for storing the nodes of tree and we will keep a flag which will alternate it's
value at every level.Once you push the left and right node at back and pop from front.and second time
you push right and left from from and pop from back.
*/
class Solution{
    public:
    vector <int> zigZagTraversal(Node* root)
    {
        vector <int> ans;
        deque<Node*> q;
        q.push_back(root);
        bool flag=true;
        while(!q.empty()){
            int k=q.size();
            for(int i=0;i<k;i++){
                Node *temp;
                if(flag){
                    temp=q.front();
                    q.pop_front();
                    ans.push_back(temp->data);
                    if(temp->left) q.push_back(temp->left);
                    if(temp->right) q.push_back(temp->right);

                }
                else{
                    temp=q.back();
                    q.pop_back();
                    ans.push_back(temp->data);
                    if(temp->right) q.push_front(temp->right);
                    if(temp->left) q.push_front(temp->left);
                }
            }
            flag=!flag;
        }
        return ans;
    }
};