102. Binary Tree Level Order Traversal

📝 Problem Details

• Title: 102. Binary Tree Level Order Traversal
• Link: https://leetcode.com/problems/binary-tree-level-order-traversal/
• Difficulty: Medium
• Tags/Categories: BFS Trees Queue

💭What Were My Initial Thoughts?

- perform a BFS to traverse the tree level by level
- store each level's nodes in a vector
- return a vector of vectors containing all levels

💡 Explanation of Solution

1. Use a Queue for BFS
	- a queue helps track nodes at each level 
	- start by pushing the root node into the queue

2. Process Each Level
	- while the queue is not empty
		- get the number of nodes at the current level (`levelSize`)
		- iterate through levelSize nodes, adding their values to the currentLevel vector
		- add their children to the queue for processing in the next iteration

3. Store and Return Results

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        // base case: if root is nullptr return empty vector
        if(root == nullptr) return {};
        vector<vector<int>> res;
        // use a queue to keep track of nodes at each level 
        queue<TreeNode*> q;
        q.push(root); // start with the root of the tree 
 
        while(!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;
 
            for(int i = 0; i < levelSize; i++) {
                TreeNode* current = q.front();
                q.pop();
                currentLevel.push_back(current->val);
                if(current->left) q.push(current->left);
                if(current->right) q.push(current->right);   
            }
            res.push_back(currentLevel);
        }
        return res;
    }
};