← Back to DSA Course | Chapter 11: Trees | Lesson 3 of 10

Level Order Traversal BFS

Level order traversal is like visiting a family tree generation by generation: first the grandparent, then all their kids, then all their grandkids.

In this page:

  1. BFS Idea
  2. Queue in BFS
  3. Level Information
  4. BFS Applications
  5. BFS Practice
Syntax
markup 
from collections import deque
queue = deque([root])
while queue:
    node = queue.popleft()
    visit(node)
    if node.left:
        queue.append(node.left)
    if node.right:
        queue.append(node.right)

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;
}

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;
}

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;
}

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;
}

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;
}
Related Topics

BFS Breadth First Search · Array Traversal and Operations · Tree Traversals Inorder Preorder Postorder · Binary Search Tree

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Using a stack instead of a queue, which gives depth-first order.
  2. Not saving queue.size() before the level loop, so the level boundary changes as children are added.
  3. Pushing nullptr children into the queue and then dereferencing them.
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Tree Traversals Inorder Preorder Postorder Next Lesson → Binary Search Tree

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.