curr variable has a reference to root in the first iteration of while loop, but starting from the second iteration curr variable should have a reference to a newly created node every iteration?
var TreeNode = function (value, left, right) {
this.value = value;
this.left = left;
this.right = right;
};
function arrayToTree(array) {
if (!array.length) return undefined;
var root = new TreeNode(array.shift());
var queue = [root];
while (array.length) {
var curr = queue.shift();
var left = new TreeNode(array.shift());
curr.left = left;
queue.push(left);
if (!array.length) break;
var right = new TreeNode(array.shift());
queue.push(right);
curr.right = right;
}
return root;
};
const ret = arrayToTree([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
console.log(ret);The root variable just references the root object. That doesn't change during the process of extension. But during that process, the left and right properties of that object change value (from null to a new node).
In the first iteration of the loop, curr gets to reference the same object as root, and so whatever mutation is brought to curr is brought to root: both variables are giving access to the same single object. As the code sets curr.left to a new node and sets curr.right to a new node, at that moment root.left and root.right have been set to new nodes.
In the next iteration, curr will reference one of those newly created nodes (which are already "attached" to root), and the same happens there: as curr is mutated, we actually mutate a node that can be reached from root. That deeper node gets extended with new nodes referenced by its left and/or right properties.
I think trincot answered your question. If that isn't clear, please comment.
But if you want a version of this that involves no mutation, you can do it recursively, by noting that the left child of the node formed from the value at index i is the one formed from the value at index 2 * i + 1 and the right child from the value at index 2 * i + 2, assuming they exist:
const toTree = (xs, i = 0) =>
i >= xs .length
? undefined
: {value: xs [i], left: toTree (xs, 2 * i + 1), right: toTree (xs, 2 * i + 2)}
console .log (toTree ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])).as-console-wrapper {max-height: 100% !important; top: 0}This does not use your TreeNode constructor. Unless there's more to it than is shown, I see no reason for it. But if we need to use it, we could replace this:
: {value: xs [i], left: toTree (xs, 2 * i + 1), right: toTree (xs, 2 * i + 2)}
with this:
: new TreeNode (xs [i], toTree (xs, 2 * i + 1), toTree (xs, 2 * i + 2))