Problem Statement

Given a binary tree, perform a level order traversal. In level order traversal, the nodes are visited level by level from left to right.

Examples

Example 1:

Consider the following binary tree:

        1
       / \
      2   3
     / \
    4   5

The level order traversal of the above tree is:
1, 2, 3, 4, 5

Explanation:
1 (because 1 is at level 1)
2, 3 (2, 3, is at same level)
4, 5 (4, 5 is at same level)

Different Approach

1️⃣ Queue Based Approach

Intuition:

To traverse a binary tree level by level and capture the values of nodes at each level, we use a method known as level-order traversal. This approach involves examining nodes one level at a time, starting from the root and moving downward through the tree. By using a queue to keep track of nodes at each level, we ensure that nodes are processed in the order they appear at each level. This method efficiently organizes nodes into a 2D structure where each sub-array represents a level of the tree, capturing the complete structure of the tree from top to bottom.

Approach:

To perform a level-order traversal iteratively, follow these steps:

1. Start by initializing an empty queue to hold nodes as we traverse the tree level by level.
2. Enqueue the root node into the queue. If the tree is empty, return an empty 2D vector immediately.
3. While the queue is not empty, process each level of the tree:
   1. Determine the number of nodes at the current level by checking the size of the queue.
   2. Create a temporary vector to store the values of nodes at this level.
   3. For each node at the current level:
      1. Dequeue the front node from the queue.
      2. Store the node’s value in the temporary vector.
      3. Enqueue the left and right children of the current node (if they exist) into the queue.
   4. After processing all nodes at the current level, add the temporary vector to the final 2D vector representing the level order traversal.
4. Once all levels are processed, return the 2D vector containing the level-order traversal of the binary tree.

Code:

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

// Definition for a binary tree node.
struct TreeNode {
    int data; 
    TreeNode* left; 
    TreeNode* right;

    // Constructor with a value parameter for TreeNode
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to perform level-order traversal of a binary tree
    vector<vector<int>> levelOrder(TreeNode* root) {
        // Create a 2D vector to store levels
        vector<vector<int>> ans; 
        if (root == nullptr) {
            // If the tree is empty, return an empty vector
            return ans; 
        }
        
        // Create a queue to store nodes for level-order traversal
        queue<TreeNode*> q; 
        // Push the root node to the queue
        q.push(root); 

        while (!q.empty()) {
            // Get the size of the current level
            int size = q.size(); 
            // Create a vector to store nodes at the current level
            vector<int> level; 

            for (int i = 0; i < size; i++) {
                // Get the front node in the queue
                TreeNode* node = q.front(); 
                // Remove the front node from the queue
                q.pop(); 
                // Store the node value in the current level vector
                level.push_back(node->data); 

                // Enqueue the child nodes if they exist
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            // Store the current level in the answer vector
            ans.push_back(level); 
        }
        // Return the level-order traversal of the tree
        return ans; 
    }
};

// Function to print the elements of a vector
void printVector(const vector<int>& vec) {
    // Iterate through the vector and print each element
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;
}

// Main function
int main() {
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // Create an instance of the Solution class
    Solution solution; 
    // Perform level-order traversal
    vector<vector<int>> result = solution.levelOrder(root); 

    cout << "Level Order Traversal of Tree: "<< endl;

    // Printing the level order traversal result
    for (const vector<int>& level : result) {
        printVector(level);
    }

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) where N is the number of nodes in the binary tree. Each node of the binary tree is enqueued and dequeued exactly once, hence all nodes need to be processed and visited. Processing each node takes constant time operations which contributes to the overall linear time complexity.
• Space Complexity:O(N) where N is the number of nodes in the binary tree. In the worst case, the queue has to hold all the nodes of the last level of the binary tree; the last level could at most hold N/2 nodes, hence the space complexity of the queue is proportional to O(N). The resultant vector answer also stores the values of the nodes level by level and hence contains all the nodes of the tree contributing to O(N) space as well.