LeetCode Solution 102 - Binary Tree Level Order Traversal

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:

    3
   / \
  9  20
    /  \
   15   7

Output:

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

Optimal Approach

Breadth-First Search (BFS) Using Queue

The most efficient way to perform a level order traversal is to use a queue. BFS processes nodes level by level, ensuring each node is visited in the correct order.

Algorithm Steps:

1. Initialize an empty queue and add the root node.
2. While the queue is not empty:
   • Determine the number of nodes at the current level.
   • Process each node at this level, adding its value to the result list.
   • Add its left and right children to the queue if they exist.
3. Repeat until all levels are processed.

LeetCode-Compatible C++ Solution

#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            
            for (int i = 0; i < size; 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;
    }
};

Step-by-Step Explanation of Code

1. Queue Initialization: A queue is used to keep track of nodes at each level.
2. Loop through Levels: We process all nodes at a given level before moving to the next level.
3. Store Level Values: Extract node values and store them in a 2D vector.
4. Add Children to Queue: Left and right children of each node are added to the queue for processing in the next iteration.

Dry Run / Execution Steps

Input:

    3
   / \
  9  20
    /  \
   15   7

Execution:

Queue Content	Level Nodes	Output
[3]	[3]	[[3]]
[9,20]	[9,20]	[[3],[9,20]]
[15,7]	[15,7]	[[3],[9,20],[15,7]]

Alternative Approaches

1. Recursive DFS Approach

Instead of BFS, we can use a recursive approach with depth tracking.

Time Complexity: O(N)

Space Complexity: O(N) (due to recursion stack)

class Solution {
public:
    void dfs(TreeNode* root, vector<vector<int>>& result, int level) {
        if (!root) return;
        if (result.size() == level) result.push_back({});
        
        result[level].push_back(root->val);
        dfs(root->left, result, level + 1);
        dfs(root->right, result, level + 1);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        dfs(root, result, 0);
        return result;
    }
};

Best Solution & Why It’s Best

Approach	Time Complexity	Space Complexity	Reason
BFS (Queue)	O(N)	O(N)	Iterative and efficient
DFS (Recursion)	O(N)	O(N)	Requires additional recursion stack space

BFS using a queue is the best choice because it ensures an intuitive level-order traversal with minimal space overhead compared to the recursive approach.

Complexity Analysis

• Time Complexity: O(N) since we visit each node once.
• Space Complexity: O(N) due to queue storage.

Conclusion

• The BFS approach using a queue is the most efficient solution.
• Recursive DFS is an alternative but has higher space complexity.
• Similar Problems for Practice:
  • Binary Tree Zigzag Level Order Traversal
  • Binary Tree Right Side View
  • Populating Next Right Pointers in Each Node