0
$\begingroup$

I have this algorithm to sum binary tree branches from leftmost branch to rightmost one, so the solution is an array of sums:

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function branchSums(root) {
  let sums = [];
    _doSum(root, 0, sums);
    return sums;
}

function _doSum(root, currentSum, sums) {
    if (!root) {
        return;
    }
    if (!root.left && !root.right) {
        sums.push(currentSum + root.value);
    } else {
        _doSum(root.left, currentSum + root.value, sums);
        _doSum(root.right, currentSum + root.value, sums);
    }
}

It's working fine, but now I'm trying to solve the same problem in an iterative fashion.

I have tried this:

function branchSums(root) {
  let stack = [];
    let sums = [];
    let sum = 0;
    stack.push(root);
    while (stack.length > 0) {
        const node = stack.pop();
        sum += node.value;
        if (!node.right && !node.left) {
            sums.push(sum);
            sum -= node.value;
            continue;
        }
        if (node.right) {
            stack.push(node.right);
        }
        if (node.left) {
            stack.push(node.left);
        }
    }
    return sums;
}

But it doesn't work. After debugging, I have noticed that the error is because I'm only decreasing sum when I reach a leaf node, after pushing to sums. But I need to do it also when depth changes. I don't know how to explain it.

Is it possible to wirte an iterative solution to this problem?

$\endgroup$
1
  • 1
    $\begingroup$ It certainly is possible, as every recursive algorithm can be written as an iterative one, using a stack as you do. It gets more complicated when you have a >1 branching factor in the recursive version. This might be helpful: stackoverflow.com/questions/159590/… (take a look at the 2nd and 3rd answers in particular) $\endgroup$ – CSSTUDENT Nov 25 '20 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.