algoadvance

Leetcode 102. Binary Tree Level Order Traversal

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

Clarifying Questions

1. What should be returned if the tree is empty (i.e., the root is NULL)?
   • The function should return an empty vector.
2. Can we assume the tree nodes contain only integer values?
   • Yes, for simplicity, we can assume the nodes contain integer values.

Strategy

1. Use a queue to facilitate level order traversal:
   • We will use a queue to keep track of nodes at each level.
   • Start by pushing the root node into the queue.
   • Iterate while the queue is not empty, processing nodes level by level.
2. Process nodes level by level:
   • For each level, determine the number of nodes at that level (i.e., the size of the queue).
   • Process nodes one by one, adding their children to the queue.
   • Collect the node values for the current level in a temporary vector and then add this vector to the result vector.

Code

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

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

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) {
            return result;  // Return an empty result if the tree is empty.
        }
        
        queue<TreeNode*> q;  // Queue for storing nodes at each level.
        q.push(root);
        
        while (!q.empty()) {
            int level_size = q.size();  // Number of nodes at the current level.
            vector<int> current_level;  // To store node values at the current level.
            
            for (int i = 0; i < level_size; ++i) {
                TreeNode* node = q.front();
                q.pop();
                current_level.push_back(node->val);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            result.push_back(current_level);  // Add the current level to the result.
        }
        
        return result;
    }
};

Time Complexity

• O(n): Where n is the number of nodes in the tree. This is because we visit each node exactly once.

Space Complexity

• O(n): In the worst case, the queue (and the resulting vector) will store all nodes of the tree. This happens when the tree is completely unbalanced (e.g., a linked list). In the case of a balanced tree, the space complexity would be less but still proportional to the number of nodes in the tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?