Binary Tree Level Order Traversal medium

Problem Statement

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

Example 1

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

Example 2

Input: root = [1] Output: [[1]]

Steps

1. Initialization: Create a queue to store nodes for level-order traversal and a list to store the results. Enqueue the root node if it exists.

2. Level Traversal: While the queue is not empty:

   • Get the size of the queue (this represents the number of nodes at the current level).
   • Create a temporary list to store nodes' values at the current level.
   • Dequeue nodes from the queue (size number of nodes). For each dequeued node:
     • Add its value to the temporary list.
     • Enqueue its left child (if it exists).
     • Enqueue its right child (if it exists).
   • Add the temporary list (representing the current level's values) to the results list.

3. Return Result: Return the results list.

Explanation

The algorithm uses a Breadth-First Search (BFS) approach. The queue acts as a FIFO (First-In, First-Out) structure, ensuring that nodes are processed level by level. By tracking the queue size at each iteration, we accurately process all nodes within a level before moving to the next. This guarantees the correct level order traversal.

Code

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        IList<IList<int>> result = new List<IList<int>>();
        if (root == null) return result;

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

        while (queue.Count > 0) {
            int levelSize = queue.Count;
            IList<int> currentLevel = new List<int>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
                currentLevel.Add(node.val);

                if (node.left != null) {
                    queue.Enqueue(node.left);
                }
                if (node.right != null) {
                    queue.Enqueue(node.right);
                }
            }
            result.Add(currentLevel);
        }
        return result;
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed exactly once.
• Space Complexity: O(W), where W is the maximum width (maximum number of nodes at any level) of the tree. In the worst-case scenario (a complete binary tree), W can be equal to N. The space used by the queue dominates the space complexity.