Search code examples
javascripttreetree-traversal

429. N-ary Tree Level Order Traversal - std::bad_alloc

I am trying to solve the leetcode problem 429. N-ary Tree Level Order Traversal

I have used the basic level order traversal concept as shown below

var levelOrder = function(root) {
    let queue = [root, null];
    let result = [];
    let tmp = [];
    
    for(let i=0; i<queue.length; i++){
        let node = queue[i];
        
        if(!node){
            result.push(tmp);
            tmp = new Array();
            if(i !== queue.length-1) queue.push(null);
        }else{
             queue = [...queue, ...node.children];
            tmp.push(node.val);
        }
    }
    return result;
};

I tried running the sample Test-Cases Provided:

TC-1

enter image description here

TC-2

enter image description here

Problem

While submitting the same code I get to see the below error: enter image description here

Can someone please explain what is going wrong here and what needs to be fixed?

Solution

  • The problem occurs when the test case passes an empty tree to your function, i.e. root is null.

    In that case, the loop keeps adding null values to the queue.

    So add a null check in your function:

    if (!root) return [];