Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

183
Visualizações
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 Respostas
Responde à pergunta

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 Relatório

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 Relatório

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 Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda