Skip to content

Instantly share code, notes, and snippets.

@a-x-
Created April 3, 2016 10:05
Show Gist options
  • Select an option

  • Save a-x-/f13e8d6fc4791e4f8a0cd7486a95b67a to your computer and use it in GitHub Desktop.

Select an option

Save a-x-/f13e8d6fc4791e4f8a0cd7486a95b67a to your computer and use it in GitHub Desktop.
Sum tree with data stack (no call stack). Breadth first traversal
function sumTree (tree) {
var sum = tree.value;
var root = tree;
var stack = [root.next];
while(stack.length) {
sum = stack.pop().reduce((sum, root) => {
stack.push(root.next);
return sum + root.value;
}, sum);
}
return sum;
}
var tree = {
"value": 5,
"next": [
{
"value": 3,
"next": [
{
"value": 3,
"next": []
}, {
"value": 5,
"next": []
},{
"value": 3,
"next": []
}, {
"value": 5,
"next": []
}
]
}, {
"value": 5,
"next": []
},{
"value": 3,
"next": [
{
"value": 3,
"next": []
}, {
"value": 5,
"next": []
},{
"value": 3,
"next": []
}, {
"value": 5,
"next": []
}
]
}, {
"value": 5,
"next": []
}
]
};
sumTree(tree);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment