How to fix the bug of arrayToTree function？

[yuan0221]

I found a bug in the arrayToTree function, I tried to modify the logic of arrayToTree, but it didn't solve the problem, please help me！Here are the details:

• input

const arr = [1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15];

• wrong output

        /——— 7
       |    \——— 12
    /——— 3
   |    \——— 6
——— 1
    \——— 2
       |    /——— 9
        \——— 4
           |    /——— 15
            \——— 8

• The correct output should be

            /——— 15
        /——— 7
    /——— 3
   |    \——— 6
   |        \——— 12
——— 1
    \——— 2
       |    /——— 9
        \——— 4
            \——— 8

• The location of the arrayToTree function

hello-algo/codes/javascript/modules/TreeNode.js

• my question
  If you want to pass the above case, how to modify the logic of the arrayToTree function？

[krahets]

The arrToTree() function of JS is out of date. Could you please update it to match the Python(or Java, C++)'s implementation?

https://github.com/krahets/hello-algo/blob/main/codes/python/modules/tree_node.py

[krahets]

@justin-tse Please track this issue, thanks!

[krahets]

@justin-tse Please track this issue, thanks!

[yuan0221]

The arrToTree() function of JS is out of date. Could you please update it to match the Python(or Java, C++)'s implementation?

https://github.com/krahets/hello-algo/blob/main/codes/python/modules/tree_node.py

Recursion is ok (that's what java does), but I just wonder if it can be achieved using a queue (arrayToTree in js)?

[chinesedfan]

Of course, just also push null into the queue.

function arrToTree(arr) {
    if (arr.length === 0) return null;

    const root = new TreeNode(arr[0]);
    const queue = [root];
    let i = 0;
    while (queue.length) {
        const node = queue.shift();
        if (node) {
            if (++i >= arr.length) break;
            if (arr[i] !== null) node.left = new TreeNode(arr[i]);
            if (++i >= arr.length) break;
            if (arr[i] !== null) node.right = new TreeNode(arr[i]);
            queue.push(node.left, node.right)
        } else {
            i += 2;
            queue.push(null, null)
        }
    }

    return root;
}

[yuan0221]

Of course, just also push null into the queue.

function arrToTree(arr) {
    if (arr.length === 0) return null;

    const root = new TreeNode(arr[0]);
    const queue = [root];
    let i = 0;
    while (queue.length) {
        const node = queue.shift();
        if (node) {
            if (++i >= arr.length) break;
            if (arr[i] !== null) node.left = new TreeNode(arr[i]);
            if (++i >= arr.length) break;
            if (arr[i] !== null) node.right = new TreeNode(arr[i]);
            queue.push(node.left, node.right)
        } else {
            i += 2;
            queue.push(null, null)
        }
    }

    return root;
}

Thank you very much, you solved my confusion, thanks again for the great code. hh

[krahets]

I think this implementation might fail for the cases ended by null. But I didn't try it. Could you please test this case:

const arr = [1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, null];

[yuan0221]

I think this implementation might fail for the cases ended by null. But I didn't try it. Could you please test this case:

const arr = [1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, null];

Passed this case, and I tested that all places where arrToTree is used in the code can output correctly.

        /——— 7
    /——— 3
   |    \——— 6
   |        \——— 12
——— 1
    \——— 2
       |    /——— 9
        \——— 4
            \——— 8

[krahets]

It works well