Leetcode 662. Maximum Width of Binary Tree Javascript FlatMap attempt - Time Limit Exceeded

Question

Problem Statement:

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.

It is guaranteed that the answer will in the range of 32-bit signed integer.

I am trying to solve this Binary Tree problem. I am using an approach which uses flat maps and which seems conceptually correct by running via the terminal on the first test case. However, pasting the code inside Leetcode gives “Time Limit Exceeded” error. Here is my implementation.

var widthOfBinaryTree = function(root) {
    if ([undefined, null].includes(root)) {
        return 0
    }
    
    let frontierRef = [root]

    result = 1
    while (frontierRef[0] !== undefined) { //Empty or not
        let newElements = frontierRef.flatMap(function (node) {
            if (node) {
                return [node.left, node.right]
            } else {
                return [null, null]
            }
         }) 

        let lastNonNullPos = 0;
        //Find the first non-null element
        for (let i = newElements.length - 1; i > -1; i--) {
            if (newElements[i]) { 
                lastNonNullPos = i;
                break; 
            }
        }
        //Get all the nodes from the first till the last non-null node, inclusive
        newElements = newElements.slice(0, lastNonNullPos + 1);


        result = Math.max(newElements.length, result)
        frontierRef = newElements;
    }

    return result
 
};

I would like to ask if anyone knows what could be the slow operation and how to optimize it to make it runnable. Let me know if more information is required to solve the problem.

Answer 1

The bug

The code doesn't terminate, because the loop condition frontierRef[0] !== undefined will never be false. After the last level of the tree, newElements will have all null values, the slice will slice off all but the first element, so the loop will evaluate null !== undefined, true forever.

Slow algorithm

The algorithm itself is too slow to solve this puzzle. The algorithm is essentially brute force: for each level in the tree, build an array of values, replacing nodes with their children, or if the node is null, then replace with two null, making the level "complete", so you can count the width exactly.

I think Leetcode problems at medium level are generally hard enough that you need something better than brute force. In this example, you can expect test data sets with sparse trees. In the extreme, consider the degenerate tree that's really a line of right-leafs. The current program will build up an array of many null values, ending with the non-null leaf. In every iteration the size of the array will double. The problem description says there can be 3000 nodes, so you'll end up with an array of 2²⁹⁹⁹ elements.

Here's a hint: consider labeling the leaves of a complete binary tree, for example:

     /         \
   /   \     /   \
  /\   /\   /\   /\
 0  1 2  3 4  5 6  7

That is, as you traverse from top to bottom to any leaf, if you build up a number from bits, appending 0 when taking a left branch and appending 1 when taking a right branch, you arrive at those number labels.

As you traverse from top to bottom, track the non-null nodes only, and their numbers. The width of the tree is the difference between the number of the rightmost node and the leftmost node + 1.

The numbers can become very big, leading to arithmetic overflows. Notice this hint in the description: It is guaranteed that the answer will in the range of 32-bit signed integer.

Slow operations

Using flatMap, for each node the code creates an array. Object creation can be expensive. It would be faster to initialize a target array, use a classic loop and append elements to the target array, because much fewer objects will be created.

Checking if an array is empty

I think this is a strange way to check if an array is empty:

while (frontierRef[0] !== undefined) { //Empty or not

It would be more idiomatic to use a condition on the length property.

Unnecessary code

This condition is unnecessary when solving this leetcode problem:

if ([undefined, null].includes(root)) {
    return 0
}

It's unnecessary because the constraints (on the website) state:

The number of nodes in the tree is in the range [1, 3000].

I recommend to always read carefully the constraints. They can help you avoid implementing unnecessary checks, as well as give an idea of the level of complexity involved in the puzzle. For example here, if the range of values was [1, 10] then the brute-force algorithm would be probably just fine. With [1, 3000] it clearly cannot work.