Tree traversal, passed variable is reset to 0 when exiting the final recursion (Javascript)-CodePudding

Can someone explain to me why given this code to traverse a binary tree:

var sumOfLeftLeaves = function(root) {
    let sum = 0;
    traverse(root, sum);
    return sum;
};


function traverse(root, sum) {

    const left = root.left;
    const right = root.right;


    if (left) {
        sum  = left.val;
        traverse(left, sum);
    }

    if (right) {
        traverse(right, sum);
    }

}

the sum that has been correctly calculated during the traversal of the tree, is reset to 0 after exiting the last recursive stage?

CodePudding user response：

var sumOfLeftLeaves = function(root) {
    let sum = 0;
    return traverse(root, sum);
};


function traverse(root, sum) {

    const left = root.left;
    const right = root.right;

    sum  = root.val
    if (left) {
        sum  = traverse(left, sum);
    }

    if (right) {
        sum  = traverse(right, sum);
    }
    return sum

}

sum is an immutable value. This means that each time you pass it as an argument to a function call a new copy is made. Therefore, the additions you make further down the recursive stack are not reflected on the sum variable in the stack frames above.

To further elaborate, sum is an integer, Number in JS terms. It is a value type, meaning that on each assignment, it is passed by value, copied over. In other words, the JS runtime, creates a new place on the stack and stores the value that was assigned in the new place. Any mutation/modification you do on the value type, is not reflected on original variable.

This approach solves the problem.

Another approach would be to remove sum as a parameter and only return the sum of the node values as follows:

var sumOfLeftLeaves = function(root) {
    return traverse(root);
};


function traverse(root) {
    if (root == null) return 0

    return root.val   traverse(root.left)   traverse(root.right);
}

For completeness sake, a third approach would be to make sum a mutable variable, like a js object type or an array. While the object's or array's structure itself is passed by value, their contents can be changed and those changes will be reflected in the original variable. Let's say you pass sum as an array of one element, const sum = [0]. Whenever you add something to it, sum[0] = node.val, the value of the element at index zero of sum changes and is also visible to functions further above the call stack.

CodePudding user response：

You're not returning sum from traverse, and not reassigning it in sumOfLeftLeaves either. You probably want something more like this:

var sumOfLeftLeaves = function(root) {
    return traverse(root, 0);
};


function traverse(root, sum) {
    const left = root.left;
    const right = root.right;

    if (left) {
        sum  = left.val;
        return traverse(left, sum);
    }

    if (right) {
        return traverse(right, sum);
    }

    return sum;
}

CodePudding user response：

You could take a single function which returns either the value plus left and right side or zero.

const
    sumOfTree = node => node
        ? value   sumOfTree(node.left)   sumOfTree(node.right)
        : 0;

Another solution could be to use a traverse function which takes a node and a function with a closure over an object for the value.

const
    traverse = (node, fn) => {
        if (!node) return;
        fn(node);
        traverse(node.left, fn);
        traverse(node.right, fn);
    },
    sumOfTree = result => node => result.sum  = node.value;

// call
const
    result = { sum: 0 },
    getSum = sumOfTree(result);

traverse(tree, getSum);
console.log(result.sum);