102. Binary Tree Level Order Traversal (BFS) - Leetcode Solution
Solution codeđź’ˇ Step-by-Step Thought Process
- Understand the problem: Return the level-order traversal of a binary tree as a list of lists, where each list contains the node values at a given level.
- Check if the root is None; if so, return None.
- Initialize a deque and append the root node to it.
- Initialize an empty list (ans) to store the result.
- While the deque is not empty, process each level:
- Create an empty list (level) to store the current level’s node values.
- Get the number of nodes (n) at the current level from the deque’s length.
- For each of the n nodes, pop the leftmost node, append its value to the level list, and append its left and right children (if they exist) to the deque.
- Append the level list to the result list (ans).
- Return the result list (ans).
Code Solution
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return None
queue = deque()
queue.append(root)
ans = []
while queue:
level = []
n = len(queue)
for i in range(n):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
ans.append(level)
return ans
# Time Complexity: O(n)
# Space Complexity: O(n)
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> level;
int n = q.size();
for (int i = 0; i < n; ++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);
}
ans.push_back(level);
}
return ans;
}
};
import java.util.*;
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int n = queue.size();
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
ans.add(level);
}
return ans;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (!root) return [];
const ans = [];
const queue = [root];
while (queue.length > 0) {
const level = [];
const n = queue.length;
for (let i = 0; i < n; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
ans.push(level);
}
return ans;
};
Detailed Explanation
Understanding the Problem: Binary Tree Level Order Traversal
The “Binary Tree Level Order Traversal” problem requires us to return the values of a binary tree’s nodes, level by level, from top to bottom and left to right. This kind of traversal is also known as Breadth-First Search (BFS), where we explore all nodes at the current level before moving on to the next level. The output should be a list of lists, where each inner list contains the values of the nodes at one level of the tree.
For instance, given a binary tree with root 1 and children 2 and 3, the output would be [[1], [2, 3]], representing level 0 and level 1 of the tree respectively.
Approach: Breadth-First Search Using a Queue
To perform level order traversal, we make use of a queue (typically implemented with a deque in Python). We begin by placing the root node in the queue. Then, for each iteration, we determine how many nodes are present at the current level by checking the length of the queue. We process each of those nodes: extracting them from the queue, recording their values, and then enqueueing their children for the next level.
After processing all nodes at the current level, we append the list of values for that level to our result list. This continues until the queue is empty, which means we’ve visited all levels of the tree. This structure ensures that nodes are processed in strict left-to-right order across levels, satisfying the requirements of level order traversal.
Time and Space Complexity
The time complexity of this approach is O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once and processed in constant time. The space complexity is also O(n), which is the maximum number of nodes that can be held in the queue at any time. This typically occurs at the last level of the tree, especially in complete or full binary trees.
Edge Cases to Consider
If the input tree is empty (i.e., the root is null), the function should return an empty list. Also, for trees with only one node, the result should be a single-element list containing that node’s value. It’s important that each level in the result is a separate list, even if it contains only one value.
Conclusion
The “Binary Tree Level Order Traversal” problem is a classic application of the breadth-first search pattern. It helps reinforce the understanding of queue-based traversal techniques and is a foundational problem for anyone learning about tree data structures. The approach generalizes well and is a stepping stone to more advanced tree traversal variants such as zigzag level order and vertical order traversal.