Binary Tree Level Order Traversal 🧠

LeetCode Link: Binary Tree Level Order Traversal

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 102 - Binary Tree Level Order Traversal

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

Intuition: To perform a level order traversal of a binary tree, we can utilize a breadth-first search (BFS) algorithm. By visiting the nodes in a breadth-first manner, we can easily track the nodes at each level and store their values.

Approach:

1. Create a result vector to store the level order traversal.
2. Create a queue to perform the BFS.
3. Enqueue the root node into the queue.
4. While the queue is not empty:

• Get the current size of the queue to represent the number of nodes at the current level.
• Create a level vector to store the values of the nodes at the current level.
• Iterate through the nodes at the current level:
• Dequeue a node from the queue.
• Add the value of the dequeued node to the level vector.
• Enqueue the left and right children of the dequeued node, if they exist.
• Add the level vector to the result vector.

5. Return the result vector.

⌛ Time Complexity: The time complexity of the approach is O(n), where n is the number of nodes in the binary tree. We visit each node once during the BFS.

💾 Space Complexity: The space complexity is O(m), where m is the maximum number of nodes at any level in the binary tree. This is the space used by the queue and the result vector.

Solutions 💡

Cpp 💻

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
  public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        vector<vector<int>> result;

        if (root == nullptr) {
            return result;
        }

        queue<TreeNode *> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> level;

            for (int i = 0; i < levelSize; i++) {
                // Dequeue a node from the queue
                TreeNode *node = q.front();
                q.pop();
                // Add the value of the dequeued node to the level vector
                level.push_back(node->val);

                // Enqueue the left and right children of the dequeued node, if they exist
                if (node->left != nullptr) {
                    q.push(node->left);
                }

                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }

            // Add the level vector to the result vector
            result.push_back(level);
        }

        return result;
    }
};

Python 🐍

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        result = []
        queue = [root]

        while queue:
            level = []
            next_level = []

            for node in queue:
                level.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)

            result.append(level)
            queue = next_level

        return result