ProgramGuru

Level Order Traversal of a Binary Tree using Iteration

Problem and examples

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.
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

Explore Level Order Traversal of a Binary Tree - Iteration

Load an example or enter your own input. Use the player controls to follow each change.

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.

  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.

Implementation and efficiency

C implementation

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

C++ implementation

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> levelOrderTraversal(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        result.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return result;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    vector<int> result = levelOrderTraversal(root);
    cout << "Level order traversal: ";
    for (int val : result) cout << val << " ";
    cout << endl;
    return 0;
}

Python implementation

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

def levelOrderTraversal(root):
    if not root:
        return []
    queue = [root]
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(levelOrderTraversal(root))

Java implementation

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class IterativeLevelOrderTraversal {
    public List<Integer> levelOrderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        IterativeLevelOrderTraversal sol = new IterativeLevelOrderTraversal();
        System.out.println(sol.levelOrderTraversal(root));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function levelOrderTraversal(root) {
    if (!root) return [];
    const queue = [root];
    const result = [];
    while (queue.length) {
        const node = queue.shift();
        result.push(node.val);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return result;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log(levelOrderTraversal(root));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func levelOrderTraversal(root *TreeNode) []int {
    var result []int
    if root == nil {
        return result
    }
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node.Val)
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return result
}

func main() {
    root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}, &TreeNode{3, nil, nil}}
    result := levelOrderTraversal(root)
    fmt.Println(result)
}

Rust implementation

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn level_order_traversal(root: Option<Box<TreeNode>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut queue = VecDeque::new();
    if let Some(node) = root {
        queue.push_back(node);
    }
    while let Some(node) = queue.pop_front() {
        result.push(node.val);
        if let Some(left) = node.left {
            queue.push_back(left);
        }
        if let Some(right) = node.right {
            queue.push_back(right);
        }
    }
    result
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode::new(4))),
            right: Some(Box::new(TreeNode::new(5)),),
        })),
        right: Some(Box::new(TreeNode::new(3))),
    }));
    let result = level_order_traversal(root);
    println!("{:?}", result);
}

Kotlin implementation

import java.util.*

data class TreeNode(var `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun levelOrderTraversal(root: TreeNode?): List<Int> {
    val result = mutableListOf<Int>()
    if (root == null) return result
    val queue: Queue<TreeNode> = LinkedList()
    queue.offer(root)
    while (queue.isNotEmpty()) {
        val node = queue.poll()
        result.add(node.`val`)
        node.left?.let { queue.offer(it) }
        node.right?.let { queue.offer(it) }
    }
    return result
}

fun main() {
    val root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    println(levelOrderTraversal(root))
}

Swift implementation

import Foundation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func levelOrderTraversal(_ root: TreeNode?) -> [Int] {
    var result = [Int]()
    guard let root = root else { return result }
    var queue: [TreeNode] = [root]
    while !queue.isEmpty {
        let node = queue.removeFirst()
        result.append(node.val)
        if let left = node.left { queue.append(left) }
        if let right = node.right { queue.append(right) }
    }
    return result
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)
print(levelOrderTraversal(root))

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function levelOrderTraversal(root: TreeNode | null): number[] {
    if (!root) return [];
    const queue: TreeNode[] = [root];
    const result: number[] = [];
    while (queue.length) {
        const node = queue.shift()!;
        result.push(node.val);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return result;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log(levelOrderTraversal(root));