Published Nov 24, 2021
[
Write a function, treeSum, that takes in the root of a binary tree that contains number values. The function should return the total sum of all values in the tree.
class Node {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
const treeSum = (root) => {
// base case
if(root === null) return 0;
return root.val + treeSum(root.left) + treeSum(root.right)
};
const treeSumStack = (root) => {
if(root === null) return 0;
let sum = 0;
const stack = [root]
while(stack.length > 0) {
const current = stack.pop()
sum += current.val;
if(current.left) stack.push(current.left)
if(current.right) stack.push(current.right)
}
return sum
};
const treeSumQueue = (root) => {
if(root === null) return 0;
// todo
let sum = 0;
const queue = [root]
while(queue.length > 0) {
const current = queue.shift()
sum += current.val;
if(current.left) queue.push(current.left)
if(current.right) queue.push(current.right)
}
return sum
};
{
const a = new Node(3);
const b = new Node(11);
const c = new Node(4);
const d = new Node(4);
const e = new Node(-2);
const f = new Node(1);
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
// 3
// / \
// 11 4
// / \ \
// 4 -2 1
console.log(
treeSum(a)); // -> 21
console.log(
treeSumStack(a)); // -> 21
console.log(
treeSumQueue(a)); // -> 21
}
{
const a = new Node(1);
const b = new Node(6);
const c = new Node(0);
const d = new Node(3);
const e = new Node(-6);
const f = new Node(2);
const g = new Node(2);
const h = new Node(2);
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
e.left = g;
f.right = h;
// 1
// / \
// 6 0
// / \ \
// 3 -6 2
// / \
// 2 2
console.log(
treeSum(a)); // -> 10
console.log(
treeSumStack(a)); // -> 21
console.log(
treeSumQueue(a)); // -> 21
}
{
console.log(
treeSum(null)); // -> 0
console.log(
treeSumStack(null)); // -> 0
console.log(
treeSumQueue(null)); // -> 0
}