102. Binary Tree Level Order Traversal

Description

This problem involves traversing a binary tree in level order, which means visiting nodes level by level from left to right.

Intuition

To solve this problem, we can use a queue-based approach. Starting from the root node, we will enqueue each node and process them level by level. We will maintain a list of lists where each inner list represents nodes at a particular level.

Approach

1. Initialization: Start with an empty result list to store levels of nodes.
2. Breadth-First Traversal: Use a queue to facilitate level-order traversal. - Enqueue the root node. - While the queue is not empty: - Determine the current level size (number of nodes in the current level). - Initialize an empty list to store node values for the current level. - Iterate through the current level nodes (based on the level size): - Dequeue a node from the front of the queue. - Append its value to the current level list. - Enqueue its left and right children if they exist. - Append the current level list to the result list.
3. Completion: Once the queue is empty, all nodes have been processed, and the result list contains lists of node values by level.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the binary tree. Each node is processed exactly once.

Space Complexity:

O(N) in the worst case. This occurs when the tree is completely unbalanced, and the queue contains all nodes at the last level.

Code

C++

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector> result;
        if (root == nullptr) return result;
        
        queue queue;
        queue.push(root);
        
        while (!queue.empty()) {
            int levelSize = queue.size();
            vector currentLevel;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* currentNode = queue.front();
                queue.pop();
                
                currentLevel.push_back(currentNode->val);
                if (currentNode->left != nullptr) queue.push(currentNode->left);
                if (currentNode->right != nullptr) queue.push(currentNode->right);
            }
            
            result.push_back(currentLevel);
        }
        
        return result;
    }
};

Python

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            current_level = []
            
            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(current_level)
        
        return result

Java

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

JavaScript

var levelOrder = function(root) {
    let result = [];
    if (root === null) return result;

    let queue = [root];

    while (queue.length > 0) {
        let levelSize = queue.length;
        let currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            let currentNode = queue.shift();
            
            currentLevel.push(currentNode.val);
            if (currentNode.left !== null) queue.push(currentNode.left);
            if (currentNode.right !== null) queue.push(currentNode.right);
        }

        result.push(currentLevel);
    }

    return result;
};