Binary Tree Level Order Traversal - Practice Coding Problems

Binary Tree Level Order Traversal - Problem

Given the root of a binary tree, return the level order traversal of its nodes' values. This means visiting nodes level by level, from left to right within each level.

For example, if we have a binary tree with root value 3, left subtree with values 9, and right subtree with values 20, 15, 7 (where 15 and 7 are children of 20), we should return [[3], [9, 20], [15, 7]].

Each sub-array represents one level of the tree, ordered from top to bottom.

Input & Output

Example 1 — Complete Binary Tree

$ Input: root = [3,9,20,null,null,15,7]

› Output: [[3],[9,20],[15,7]]

💡 Note: Level 0: [3], Level 1: [9,20], Level 2: [15,7]. We traverse left to right within each level.

Example 2 — Single Node

$ Input: root = [1]

› Output: [[1]]

💡 Note: Only one node at level 0, so result is [[1]].

Example 3 — Empty Tree

$ Input: root = []

› Output: []

💡 Note: Empty tree has no levels, return empty array.

Constraints

The number of nodes in the tree is in the range [0, 2000]
-1000 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes at different levels

Level Processing

Group nodes by their depth level

Output Array

Return 2D array where each sub-array represents one level

Key Takeaway

🎯 Key Insight: BFS with queue naturally processes nodes level by level, making it perfect for this problem

Asked in

F Facebook 65 A Amazon 58 M Microsoft 42 G Google 35

The key insight is using BFS with a queue to naturally process nodes level by level. Best approach is BFS Level-by-Level using queue size tracking to separate levels cleanly. Time: O(n), Space: O(w) where w is maximum tree width.

Common Approaches

Approach	Time	Space	Notes
✓ BFS Level-by-Level	O(n)	O(w)	Use breadth-first search with queue to naturally process nodes level by level
DFS with Level Tracking	O(n)	O(h)	Use DFS to visit all nodes and group them by their depth level

BFS Level-by-Level — Algorithm Steps

Step 1: Initialize queue with root node
Step 2: For each level, process all current nodes
Step 3: Add children to queue for next level

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Queue

Start with root in queue

Process Level

Process all nodes at current level

Next Level

Add children to queue for next iteration

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

struct QueueNode {
    struct TreeNode* treeNode;
    struct QueueNode* next;
};

struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
    int size;
};

struct Queue* createQueue() {
    struct Queue* q = malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    q->size = 0;
    return q;
}

void enqueue(struct Queue* q, struct TreeNode* node) {
    struct QueueNode* temp = malloc(sizeof(struct QueueNode));
    temp->treeNode = node;
    temp->next = NULL;
    
    if (q->rear == NULL) {
        q->front = q->rear = temp;
    } else {
        q->rear->next = temp;
        q->rear = temp;
    }
    q->size++;
}

struct TreeNode* dequeue(struct Queue* q) {
    if (q->front == NULL) return NULL;
    
    struct QueueNode* temp = q->front;
    struct TreeNode* node = temp->treeNode;
    
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    
    free(temp);
    q->size--;
    return node;
}

int** solution(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int** result = malloc(1000 * sizeof(int*));
    *returnColumnSizes = malloc(1000 * sizeof(int));
    *returnSize = 0;
    
    struct Queue* queue = createQueue();
    enqueue(queue, root);
    
    while (queue->size > 0) {
        int levelSize = queue->size;
        result[*returnSize] = malloc(levelSize * sizeof(int));
        (*returnColumnSizes)[*returnSize] = levelSize;
        
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* node = dequeue(queue);
            result[*returnSize][i] = node->val;
            
            if (node->left) enqueue(queue, node->left);
            if (node->right) enqueue(queue, node->right);
        }
        
        (*returnSize)++;
    }
    
    return result;
}

struct TreeNode* buildTree(int* arr, int size) {
    if (size == 0) return NULL;
    
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = arr[0];
    root->left = root->right = NULL;
    
    struct Queue* queue = createQueue();
    enqueue(queue, root);
    int i = 1;
    
    while (queue->size > 0 && i < size) {
        struct TreeNode* node = dequeue(queue);
        
        if (i < size && arr[i] != -1001) {
            node->left = malloc(sizeof(struct TreeNode));
            node->left->val = arr[i];
            node->left->left = node->left->right = NULL;
            enqueue(queue, node->left);
        }
        i++;
        
        if (i < size && arr[i] != -1001) {
            node->right = malloc(sizeof(struct TreeNode));
            node->right->val = arr[i];
            node->right->left = node->right->right = NULL;
            enqueue(queue, node->right);
        }
        i++;
    }
    
    return root;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strstr(token, "null")) {
            arr[size++] = -1001;
        } else {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    struct TreeNode* root = buildTree(arr, size);
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(root, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in breadth-first order

✓ Linear Growth

Space Complexity

O(w)

Queue stores at most w nodes where w is maximum tree width, plus O(n) for result

✓ Linear Space

221.0K Views

High Frequency

~15 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS Level-by-Level — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler