Binary Tree Level Order Traversal - Java Solution

1. Introduction

In this post, we explore the "Binary Tree Level Order Traversal" problem. This type of traversal, also known as breadth-first search (BFS), involves visiting all nodes at each depth level of the tree before moving to the next level. It's a fundamental technique for traversing or searching a tree and is especially useful for tasks like serialization, deserialization, and finding the shortest path.

Problem

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

2. Solution Steps

1. Use a queue to facilitate level order traversal.

2. Add the root node to the queue.

3. While the queue is not empty, process each level of the tree:

a. Determine the number of elements (nodes) at the current level.

b. For each node at this level, remove it from the queue, add its value to the level's list, and add its children to the queue.

4. Continue this process for each level of the tree.

5. Return the list of lists containing the values at each level.

3. Code Program

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

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

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreeLevelOrderTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(levelOrder(root)); // Test the function
    }

    // Function for binary tree level order traversal
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

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

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

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }

            result.add(currentLevel);
        }

        return result;
    }
}

Output:

[[3], [9, 20], [15, 7]]

Explanation:

1. levelOrder: This function handles the level order traversal of a binary tree. It initializes a queue to hold the nodes at each level and a list to store the traversal result.

2. The root node is added to the queue.

3. The function enters a while loop that continues until the queue is empty, indicating that all levels have been processed.

4. Inside the loop, the size of the current level is determined. A nested for loop iterates over these nodes, adding their values to the current level's list and their children to the queue.

5. After processing each level, its list of values is added to the result list.

6. The function returns a list of lists, where each sublist represents a level in the tree with its nodes traversed from left to right.