algoadvance

Leetcode 429. N

Problem Statement

Given an n-ary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

An n-ary tree is a tree in which each node has no more than N children. Each node is defined as follows:

class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

Clarifying Questions

  1. Input Format:
    • Is the root node guaranteed not to be NULL? (Assume yes for now, but if NULL handling is needed, we will check for it).
  2. Output Format:
    • Should the output be structured as a vector of vectors containing the level-order traversal values?
  3. Constraints:
    • Can we assume that the number of nodes in the tree is within a reasonable limit so that recursion depth and space constraints are not an issue?

Strategy

To achieve the level order traversal of an n-ary tree, we can use a Breadth-First Search (BFS) approach. BFS uses a queue to traverse the tree level by level. Here’s the step-by-step plan:

  1. If the root is NULL, return an empty vector.
  2. Initialize a result vector to hold the level order traversal.
  3. Initialize a queue and push the root node into the queue.
  4. While the queue is not empty:
    • Get the number of nodes at the current level using the size of the queue.
    • Initialize a temporary vector to hold values of nodes at the current level.
    • Loop through nodes at the current level:
      • Pop the front node from the queue.
      • Add this node’s value to the temporary vector.
      • Push all children of this node into the queue.
    • Add the temporary vector to the result vector.
  5. Return the result vector.

Code

#include <vector>
#include <queue>

using namespace std;

class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        if (root == nullptr) {
            return result;
        }

        queue<Node*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;
            for (int i = 0; i < levelSize; ++i) {
                Node* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);
                for (Node* child : node->children) {
                    q.push(child);
                }
            }
            result.push_back(currentLevel);
        }
        
        return result;
    }
};

Time Complexity

The time complexity of this solution is (O(N)), where (N) is the number of nodes in the n-ary tree. Each node is processed exactly once.

Space Complexity

The space complexity is (O(N)) in the worst case, which occurs when the tree is a complete tree and the last level contains almost (N/2) nodes. This accounts for the space used by the queue.

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