Zig-Zag Traversal of Binary Tree

Given a binary tree with n nodes. Task is to find the zig-zag level order traversal of the binary tree zig zag traversal starting from the first level go from left to right for odd-numbered levels and right to left for even-numbered levels.

?? View Full Code??

Approach:

• Breadth-First Search (BFS): The problem can be solved using a BFS technique where you traverse each level of the tree one by one.
• Toggle Direction: A bool variable will be used to keep track of the current direction at each level. This will toggle after each level.
• Queue: Use a queue to store the nodes at each level. Process all nodes of the current level by extracting them from the queue, and then append their children to the queue for processing the next level.
• Vector for Reversing Order: For levels that need to be traversed in reverse, store the elements in a temporary array and reverse them before appending to the final result.

vector <int> zigZagTraversal(Node* root)
    {
    vector<int>result;
    	
    if(root == NULL){
        return result;
    }
    	
    queue<Node*>q;
    q.push(root);
    
    bool direction = true;
    	
    while(!q.empty()){
    	    
        int size = q.size();
        vector<int>ans(size);
    	    
        for(int i=0 ; i<size ; i++){
    	        
            Node* frontNode = q.front();
            q.pop();
    	        
            if(direction){
                ans[i] = frontNode->data;
            }
            else{
                ans[size-i-1] = frontNode->data;
            }
    	        
           if(frontNode->left){
                q.push(frontNode->left);
            }
            if(frontNode->right){
                q.push(frontNode->right);
            }
   
        }
    	    
        direction = !direction;
    	    
        for(auto i: ans){
            result.push_back(i);
        }
    
    }
    return result;
}        

Time Complexity: O(N)

Space Complexity: O(N)

?? View GitHub Repo??