Binary Tree Level Order Traversal medium

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

Example 2

Input: root = [1] Output: [[1]]

Steps

1. Initialization: Create an empty vector of vectors result to store the level order traversal. Create a queue q to perform Breadth-First Search (BFS). Enqueue the root node into the queue.

2. BFS Traversal: While the queue is not empty:

   • Get the size levelSize of the queue. This represents the number of nodes at the current level.
   • Create a temporary vector level to store the values of nodes at the current level.
   • Iterate levelSize times:
     • Dequeue a node from the queue.
     • Add the node's value to the level vector.
     • Enqueue the node's left child (if it exists).
     • Enqueue the node's right child (if it exists).
   • Add the level vector to the result vector.

3. Return: Return the result vector.

Explanation

The algorithm uses Breadth-First Search (BFS) to traverse the binary tree level by level. BFS ensures that nodes at the same level are processed before moving to the next level. The queue acts as a FIFO (First-In, First-Out) data structure, allowing us to process nodes in the order they appear in each level. The levelSize variable is crucial for processing each level independently. It allows us to correctly group nodes into their respective levels in the output.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> level;
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(level);
        }
        return result;
    }
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited and processed exactly once.
• Space Complexity: O(W), where W is the maximum width of the binary tree. In the worst case (a complete binary tree), W can be proportional to N. The space is mainly used by the queue to store nodes at each level. In the best case (a skewed tree), W is O(1).