Empresas
Empleos
  • Sobre nosotros
  • Soluciones
    • Publicación de vacantes
      Publica tu vacante y recibe candidatos calificados en 48h.
    • Evaluación de candidatos
      500+ pruebas técnicas y psicológicas, más anti-fraude.
    • Headhunting
      Búsqueda ejecutiva a la medida de principio a fin.
    • Nómina + EOR
      Dispersión de nómina y EOR en más de 15 países de LATAM.
  • Precios
  • Empleos

0

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

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?

about 4 years ago · Juan Pablo Isaza
3 Respuestas
Responde la pregunta

0

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;
}
about 4 years ago · Juan Pablo Isaza Denunciar

0

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.

about 4 years ago · Juan Pablo Isaza Denunciar

0

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);
about 4 years ago · Juan Pablo Isaza Denunciar
Responde la pregunta
Encuentra empleos remotos

¡Descubre la nueva forma de encontrar empleo!

Top de empleos
Top categorías de empleo
Empresas
Publicar vacante Precios Comercial
Legal
Términos y condiciones Política de privacidad
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomiéndame algunas ofertas
Necesito ayuda