SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

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<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        
        queue<TreeNode*> queue;
        queue.push(root);
        
        while (!queue.empty()) {
            int levelSize = queue.size();
            vector<int> 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<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 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;
};