# Trying to convert algorithm from recursive to iterative

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?

• 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) – CSSTUDENT Nov 25 '20 at 18:39