Level Order Traversal BFS
In this page:
BFS Idea
Level order traversal visits every node of a tree one level at a time, starting from the root and moving downward, visiting all nodes at each depth before moving to the next — this is really breadth-first search applied specifically to a tree.
Example: BFS Idea
#include <iostream>
#include <queue>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
Node c1={2,nullptr,nullptr}, c2={3,nullptr,nullptr};
Node root={1,&c1,&c2};
queue<Node*> q; q.push(&root);
while (!q.empty()) {
Node* n = q.front(); q.pop();
cout << n->val << " ";
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
return 0;
}import java.util.*;
public class Main {
static class Node { int val; Node left, right; Node(int v){val=v;} }
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2); root.right = new Node(3);
Queue<Node> q = new LinkedList<>(); q.add(root);
while (!q.isEmpty()) {
Node n = q.poll();
System.out.print(n.val + " ");
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
}
}from collections import deque
class Node:
def __init__(self, val):
self.val = val; self.left = None; self.right = None
root = Node(1)
root.left = Node(2); root.right = Node(3)
q = deque([root])
while q:
n = q.popleft()
print(n.val, end=" ")
if n.left: q.append(n.left)
if n.right: q.append(n.right)#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* queue_arr[10]; int head=0, tail=0;
void push(struct Node* n){ queue_arr[tail++] = n; }
struct Node* pop(){ return queue_arr[head++]; }
int main() {
struct Node c1={2,NULL,NULL}, c2={3,NULL,NULL};
struct Node root={1,&c1,&c2};
push(&root);
while (head < tail) {
struct Node* n = pop();
printf("%d ", n->val);
if (n->left) push(n->left);
if (n->right) push(n->right);
}
return 0;
}Login to try C/C++/Java code in the editor
Queue in BFS
A queue drives the traversal: start by enqueuing the root, then repeatedly dequeue a node, process it, and enqueue its children — this naturally processes nodes in level order because children are always enqueued after their parents.
Example: Queue in BFS
#include <iostream>
#include <queue>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
Node c1={2,nullptr,nullptr}, c2={3,nullptr,nullptr};
Node root={1,&c1,&c2};
queue<Node*> q; q.push(&root);
Node* n = q.front(); q.pop();
cout << "Dequeued " << n->val << ", enqueue its children next" << endl;
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
cout << "Queue size now: " << q.size() << endl;
return 0;
}import java.util.*;
public class Main {
static class Node { int val; Node left, right; Node(int v){val=v;} }
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2); root.right = new Node(3);
Queue<Node> q = new LinkedList<>(); q.add(root);
Node n = q.poll();
System.out.println("Dequeued " + n.val + ", enqueue its children next");
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
System.out.println("Queue size now: " + q.size());
}
}from collections import deque
class Node:
def __init__(self, val):
self.val = val; self.left = None; self.right = None
root = Node(1)
root.left = Node(2); root.right = Node(3)
q = deque([root])
n = q.popleft()
print("Dequeued", n.val, ", enqueue its children next")
if n.left: q.append(n.left)
if n.right: q.append(n.right)
print("Queue size now:", len(q))#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* queue_arr[10]; int head=0, tail=0;
int main() {
struct Node c1={2,NULL,NULL}, c2={3,NULL,NULL};
struct Node root={1,&c1,&c2};
queue_arr[tail++] = &root;
struct Node* n = queue_arr[head++];
printf("Dequeued %d, enqueue its children next\n", n->val);
if (n->left) queue_arr[tail++] = n->left;
if (n->right) queue_arr[tail++] = n->right;
printf("Queue size now: %d\n", tail - head);
return 0;
}Login to try C/C++/Java code in the editor
Level Information
Because the queue can be processed level by level (by tracking how many nodes are currently in the queue at the start of each level), level order traversal makes it easy to compute things like the number of nodes at each depth or the tree's maximum width.
Example: Level Information
#include <iostream>
#include <queue>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
Node c1={2,nullptr,nullptr}, c2={3,nullptr,nullptr};
Node root={1,&c1,&c2};
queue<Node*> q; q.push(&root);
int level = 0;
while (!q.empty()) {
int count = q.size();
cout << "Level " << level << ": ";
for (int i = 0; i < count; i++) {
Node* n = q.front(); q.pop();
cout << n->val << " ";
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
cout << endl; level++;
}
return 0;
}import java.util.*;
public class Main {
static class Node { int val; Node left, right; Node(int v){val=v;} }
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2); root.right = new Node(3);
Queue<Node> q = new LinkedList<>(); q.add(root);
int level = 0;
while (!q.isEmpty()) {
int count = q.size();
System.out.print("Level " + level + ": ");
for (int i = 0; i < count; i++) {
Node n = q.poll();
System.out.print(n.val + " ");
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
System.out.println(); level++;
}
}
}from collections import deque
class Node:
def __init__(self, val):
self.val = val; self.left = None; self.right = None
root = Node(1)
root.left = Node(2); root.right = Node(3)
q = deque([root])
level = 0
while q:
count = len(q)
print(f"Level {level}: ", end="")
for _ in range(count):
n = q.popleft()
print(n.val, end=" ")
if n.left: q.append(n.left)
if n.right: q.append(n.right)
print()
level += 1#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* queue_arr[10]; int head=0, tail=0;
int main() {
struct Node c1={2,NULL,NULL}, c2={3,NULL,NULL};
struct Node root={1,&c1,&c2};
queue_arr[tail++] = &root;
int level = 0;
while (head < tail) {
int count = tail - head;
printf("Level %d: ", level);
for (int i = 0; i < count; i++) {
struct Node* n = queue_arr[head++];
printf("%d ", n->val);
if (n->left) queue_arr[tail++] = n->left;
if (n->right) queue_arr[tail++] = n->right;
}
printf("\n"); level++;
}
return 0;
}Login to try C/C++/Java code in the editor
BFS Applications
Level order traversal is the standard approach for problems asking about shortest distances in a tree, level-by-level views of a tree (like left/right/top view), or finding the width of the widest level.
Example: BFS Applications
#include <iostream>
using namespace std;
int main() {
cout << "BFS/level order is the standard approach for shortest-distance and level-by-level view problems" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("BFS/level order is the standard approach for shortest-distance and level-by-level view problems");
}
}print("BFS/level order is the standard approach for shortest-distance and level-by-level view problems")#include <stdio.h>
int main() {
printf("BFS/level order is the standard approach for shortest-distance and level-by-level view problems\n");
return 0;
}Login to try C/C++/Java code in the editor
BFS Practice
Unlike the recursive preorder/inorder/postorder traversals, level order is naturally iterative because it relies on a queue rather than the call stack — tracing it on a small tree makes clear how the queue's contents shift as each level is processed.
Example: BFS Practice
#include <iostream>
#include <queue>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
Node c1={2,nullptr,nullptr}, c2={3,nullptr,nullptr};
Node root={1,&c1,&c2};
queue<Node*> q; q.push(&root);
cout << "Iterative (queue-driven), not recursive like preorder/inorder/postorder" << endl;
while (!q.empty()) {
Node* n = q.front(); q.pop();
cout << n->val << " ";
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
return 0;
}import java.util.*;
public class Main {
static class Node { int val; Node left, right; Node(int v){val=v;} }
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2); root.right = new Node(3);
System.out.println("Iterative (queue-driven), not recursive like preorder/inorder/postorder");
Queue<Node> q = new LinkedList<>(); q.add(root);
while (!q.isEmpty()) {
Node n = q.poll();
System.out.print(n.val + " ");
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
}
}from collections import deque
class Node:
def __init__(self, val):
self.val = val; self.left = None; self.right = None
root = Node(1)
root.left = Node(2); root.right = Node(3)
print("Iterative (queue-driven), not recursive like preorder/inorder/postorder")
q = deque([root])
while q:
n = q.popleft()
print(n.val, end=" ")
if n.left: q.append(n.left)
if n.right: q.append(n.right)#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* queue_arr[10]; int head=0, tail=0;
int main() {
struct Node c1={2,NULL,NULL}, c2={3,NULL,NULL};
struct Node root={1,&c1,&c2};
printf("Iterative (queue-driven), not recursive like preorder/inorder/postorder\n");
queue_arr[tail++] = &root;
while (head < tail) {
struct Node* n = queue_arr[head++];
printf("%d ", n->val);
if (n->left) queue_arr[tail++] = n->left;
if (n->right) queue_arr[tail++] = n->right;
}
return 0;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: