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

Level Order Traversal यानि BFS

Level order traversal एक family tree को generation by generation visit करने जैसा है: पहले grandparent, फिर उनके सभी kids, फिर उनके सभी 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 किसी tree के हर node को एक समय में एक level पर visit करता है, root से शुरू होकर नीचे की ओर move करते हुए, अगली depth पर move करने से पहले हर depth पर सभी nodes visit करते हुए — यह असल में specifically एक tree पर apply की गई breadth-first search है।

उदाहरण: 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

एक queue traversal drive करता है: root को enqueue करके शुरू करें, फिर बार-बार एक node dequeue करें, इसे process करें, और इसके children को enqueue करें — यह naturally nodes को level order में process करता है क्योंकि children हमेशा अपने parents के बाद enqueued होते हैं।

उदाहरण: 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

चूंकि queue को level by level process किया जा सकता है (हर level के शुरू में queue में अभी कितने nodes हैं यह track करके), level order traversal हर depth पर nodes की संख्या या tree की maximum width जैसी चीज़ें compute करना आसान बनाता है।

उदाहरण: 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 किसी tree में shortest distances, किसी tree के level-by-level views (जैसे left/right/top view), या widest level की width ढूंढने के बारे में पूछने वाली problems के लिए standard approach है।

उदाहरण: 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

Recursive preorder/inorder/postorder traversals के विपरीत, level order naturally iterative है क्योंकि यह call stack के बजाय एक queue पर निर्भर करता है — इसे एक छोटे tree पर trace करना साफ़ दिखाता है कि हर level process होते हुए queue की contents कैसे shift होती हैं।

उदाहरण: 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 और 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. #}
आम गलतियां
  1. एक queue के बजाय एक stack उपयोग करना, जो depth-first order देता है।
  2. Level loop से पहले queue.size() save न करना, इसलिए level boundary children जुड़ने के साथ बदलती है।
  3. nullptr children को queue में push करना और फिर उन्हें dereference करना।
🔒

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.