Level Order Traversal of a Binary Tree - Iteration - Visualization

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given a binary tree, perform a level order traversal (also known as breadth-first traversal) using an iterative approach. In this traversal, nodes are visited level by level from left to right. Return a list of values grouped by each level.

Examples❯

Input Tree Level Order Output Description
[1, 2, 3, 4, 5, null, 6]
[[1], [2, 3], [4, 5, 6]] Standard case: Tree with three levels and missing left/right children
[1]
[[1]] Edge case: Tree with a single node (root only)
[] [] Edge case: Empty tree (no nodes at all)
[1, 2, null, 3, null, null, null, 4]
[[1], [2], [3], [4]] Edge case: Tree skewed to the left only
[1, null, 2, null, null, null, 3]
[[1], [2], [3]] Edge case: Tree skewed to the right only

Solution❯

Understanding the Problem

We are given a binary tree, and we are asked to perform a Level Order Traversal. This means we have to visit nodes level by level — starting from the root, then moving to the next level (children of the root), then the next, and so on. At each level, we must traverse nodes from left to right.

To do this efficiently, we’ll use a queue, because it helps us process nodes in the order they were discovered — first-in, first-out (FIFO).

Step-by-Step Solution with Example

Step 1: Understand the Tree Structure

Let’s take an example tree: [1, 2, 3, 4, 5, null, 6].

This represents the following binary tree:

       1
     /       2     3
   /        4   5     6

Step 2: Initialize Data Structures

We will use a queue to keep track of nodes we need to visit. We also need a list to store the final result — each level will be a sublist.

Step 3: Start Traversal

We begin by pushing the root node (1) into the queue.

Now we enter a loop where we process one level at a time:

Step 4: Process Level 1

Queue has: [1]

We remove 1, add it to the current level list. Then we add its children (2 and 3) to the queue.

Result: [[1]]

Queue becomes: [2, 3]

Step 5: Process Level 2

Queue has: [2, 3]

Remove 2, add its children (4, 5). Remove 3, add its child (6).

Result: [[1], [2, 3]]

Queue becomes: [4, 5, 6]

Step 6: Process Level 3

Queue has: [4, 5, 6]

Remove all three nodes. They don’t have children, so we just collect their values.

Result: [[1], [2, 3], [4, 5, 6]]

Queue becomes empty — traversal complete.

Edge Cases

Case 1: Empty Tree

If the root is null, then there’s nothing to process. The result should be an empty list: [].

Case 2: Tree with Only Root Node

For a tree like [1], there’s only one level. Result: [[1]].

Case 3: Left-Skewed Tree

Example: [1, 2, null, 3, null, 4]

    1
   /
  2
 /
3
/
4

Each level has one node: [[1], [2], [3], [4]]

Case 4: Right-Skewed Tree

Example: [1, null, 2, null, 3, null, 4]

1
   2
       3
           4

Each level has one node: [[1], [2], [3], [4]]

Finally

Level order traversal is a classic example of using a queue to explore nodes in a breadth-first manner. By processing one level at a time and carefully enqueueing child nodes, we ensure that each node is visited in the correct order.

Edge cases like empty trees or skewed trees help reinforce the flexibility of this approach. Understanding the queue’s role makes this solution intuitive and beginner-friendly.

Algorithm Steps❯

  1. Start with the root node of the binary tree.
  2. If the tree is empty, return an empty result.
  3. Initialize a queue and enqueue the root node.
  4. While the queue is not empty, dequeue a node, record its value, and enqueue its left and right children (if they exist).
  5. Continue until the queue is empty; the recorded values represent the level order traversal.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int* levelOrderTraversal(TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    TreeNode* queue[MAX_QUEUE_SIZE];
    int front = 0, rear = 0;
    int* result = malloc(MAX_QUEUE_SIZE * sizeof(int));
    int count = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode* node = queue[front++];
        result[count++] = node->val;
        if (node->left) queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
    *returnSize = count;
    return result;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    int returnSize;
    int* res = levelOrderTraversal(root, &returnSize);
    printf("Level order traversal: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");
    free(res);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...