Leetcode 102. Binary Tree Level Order Traversal

Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

DFS Recursive Approach 1


class Solution {
    public List> levelOrder(TreeNode root) {
        List> levels = new ArrayList<>();
        if(root == null) return levels;
        dfs(root, 0, levels);
        return levels;
    }
    
    void dfs(TreeNode node, int level, List> levels){
        // If the current level is not yet in the result list, create a new level
        if (level >= levels.size()) {
            levels.add(new ArrayList<>());
        }

        // Add the current node's value to its respective level
        levels.get(level).add(node.val);

        // Recursively traverse left and right subtrees with increased level
        if (node.left != null) {
            dfs(node.left, level + 1, levels);
        }
        if (node.right != null) {
            dfs(node.right, level + 1, levels);
        }
    }
}

Time and Space Complexity: O(n)

BFS Iterative Approach 2


class Solution {
    public List> levelOrder(TreeNode root) {
        List> levels = new ArrayList<>();
        if (root == null) return levels;

        Queue queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List currentLevel = new ArrayList<>();

            // Process all nodes at the current level
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                // Enqueue left and right children if they exist
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            // Add the current level to the result
            levels.add(currentLevel);
        }

        return levels;

    }
}

Time Complexity: O(n) and Space Complexity: O(n)

See Video lecture

Leetcode 102. Binary Tree Level Order Traversal

Introduction

Binary Tree Level Order Traversal is one of the most fundamental problems in binary tree processing. It involves traversing the tree level by level, starting from the root and moving downward. This technique is often referred to as breadth-first traversal because it explores all nodes at the current level before moving on to the next level.

Problem Statement

Given the root of a binary tree, return its level order traversal. Each level of the tree should be represented as a list of values.

Example

Consider the following binary tree:

The level order traversal output is:

Approach

Binary Tree Level Order Traversal can be achieved using a queue data structure to facilitate breadth-first traversal. Nodes at each level are processed in order, and their children are enqueued for processing in the next iteration.

Steps to Solve

Initialize an empty queue and add the root node.
Iterate while the queue is not empty:

For each level, process all nodes in the queue and store their values in a list.
Add the children of the processed nodes to the queue for the next level.
Append the current level's list to the result list.

Return the result list after processing all levels.

Implementation in Java

Below is the Java implementation of the Binary Tree Level Order Traversal:


import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List> levelOrder(TreeNode root) {
        List> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                currentLevel.add(currentNode.val);

                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }

            result.add(currentLevel);
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is processed once.
Space Complexity: O(n), for the queue and the result list.

Recursive Approach

A recursive solution can also be used by traversing the tree level by level and collecting values for each level in a list. The recursion depth corresponds to the height of the tree.

Implementation


import java.util.*;

class Solution {
    public List> levelOrder(TreeNode root) {
        List> result = new ArrayList<>();
        traverse(root, 0, result);
        return result;
    }

    private void traverse(TreeNode node, int level, List> result) {
        if (node == null) {
            return;
        }

        if (level >= result.size()) {
            result.add(new ArrayList<>());
        }

        result.get(level).add(node.val);
        traverse(node.left, level + 1, result);
        traverse(node.right, level + 1, result);
    }
}

Applications

Level order traversal has numerous practical applications, including:

Tree Visualization: Helps in visualizing a tree structure level by level.
Shortest Path: Breadth-first traversal is used to find the shortest path in unweighted trees and graphs.
Serialization and Deserialization: Used in algorithms that serialize and deserialize binary trees.

Common Mistakes

Not checking for a null root before starting traversal.
Failing to handle nodes with no children correctly.
Not initializing the result list or forgetting to add nodes' children to the queue.

Edge Cases

An empty tree (return an empty list).
A tree with only one node (return a list with one level).
An unbalanced tree where nodes exist only on one side.

Sample Output

Consider the binary tree:

The level order traversal output is:

Conclusion

Binary Tree Level Order Traversal is a fundamental problem in binary tree algorithms. It teaches the use of queues for breadth-first traversal and emphasizes systematic processing of hierarchical data. Mastering this technique lays the foundation for solving more complex tree and graph traversal problems.