Level Order Traversal (BFS)

DSA · Trees

Theory

Level-order traversal visits nodes level by level from left to right using a queue. Start with the root in the queue; repeatedly remove a node, record it, and add its children. Processing the queue size at the start of each round groups nodes by level. It runs in O(n) time and uses O(w) space for the widest level w.

Why we use it

It reveals the tree level by level, which is needed for shortest-path style questions in trees.

When to use it

Use it to print levels, find the minimum depth, get the right-side view, connect nodes on the same level, or serialise trees level by level.

How it works

  1. queue = [root]
  2. Queue empty? Yes: Done. No: Pop front node, visit it.
  3. Push its left and right children
  4. Repeat level by level

Syntax

queue = deque([root])
while queue:
    for _ in range(len(queue)):
        node = queue.popleft(); visit(node)
        add node.left, node.right if present

Example

from collections import deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

root = Node(3, Node(9), Node(20, Node(15), Node(7)))

def level_order(root):
    levels, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft()
            level.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        levels.append(level)
    return levels

levels = level_order(root)
print("Levels:", levels)
print("Right side view:", [lvl[-1] for lvl in levels])

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic