Binary Tree Level Order Traversal

Problem Statement

Given a binary tree's root node, the task is to perform a level order traversal on it. This traversal involves visiting all the nodes at the current depth level from left to right before moving to the next level in the tree.

Examples

Example 1

Input:

root = [3,9,20,null,null,15,7]

Output:

[[3],[9,20],[15,7]]

Example 2

Input:

root = [1]

Output:

[[1]]

Example 3

Input:

root = []

Output:

[]

Constraints

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Approach and Intuition

The level order traversal of a binary tree, also known as breadth-first traversal, requires the traversal of nodes level by level, progressing from left to right at each level. Here's a step-by-step approach and the intuition behind it:

1. Initial Check:

   • Check if the root is null. If it is, return an empty list because there are no nodes to traverse.

2. Queue Utilization:

   • Utilize a queue to keep track of nodes at the current level. Initially, add the root to this queue.

3. Traversal:

   • While the queue is not empty:
     • Determine the number of nodes at the current level (size of the queue).
     • For each node in the current level:
       • Add it to a temporary list (current level).
       • Enqueue its children (left then right) if they exist.
     • After processing all nodes at the current level, add the temporary list to the final result list.

4. Result Compilation:

   • Continue the process until the queue is empty and all levels are processed.
   • Return the compiled list of levels.

This method ensures that all nodes on the same level are processed together, and each level is handled before moving onto the next. The constraints given allow the method to handle trees of size up to 2000 nodes comfortably, with values ranging from -1000 to 1000.

Solutions

class Solution {
public:
    vector<vector<int>> traverseLevels(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        deque<TreeNode*> deque;
        deque.push_back(root);
        int currentLevel = 0;
        while (!deque.empty()) {
            result.push_back(vector<int>());
            int nodesAtLevel = deque.size();
            for (int i = 0; i < nodesAtLevel; ++i) {
                TreeNode* currentNode = deque.front();
                deque.pop_front();
                result[currentLevel].push_back(currentNode->val);
                if (currentNode->left) deque.push_back(currentNode->left);
                if (currentNode->right) deque.push_back(currentNode->right);
            }
            currentLevel++;
        }
        return result;
    }
};