Level Order Traversal (BFS on trees) visits nodes level by level, from left to right. It uses a queue to process nodes in FIFO order: enqueue the root, then repeatedly dequeue a node, process it, and enqueue its children. This produces the breadth-first ordering of the tree.
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> result;
if (!root) return result;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int sz = q.size();
vector<int> level;
for (int i=0;i<sz;i++) {
Node* 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;
}Level order traversal is simply BFS applied to trees. A queue ensures nodes are processed in FIFO order. Enqueue root, then each dequeued node enqueues its children.
To group results by level, note the queue size before processing. Process exactly that many nodes (the current level), then the queue contains exactly the next level.
Level order traversal finds the minimum depth of a tree, connects nodes at the same level (next-right-pointer problems), prints trees level by level, and finds the width of a tree.
Quiz coming soon for this algorithm.