Skip to content

Instantly share code, notes, and snippets.

@FermiDirak
Last active February 22, 2018 17:32
Show Gist options
  • Save FermiDirak/edcb7cb28d027a0303e746dfc983d1f3 to your computer and use it in GitHub Desktop.
Save FermiDirak/edcb7cb28d027a0303e746dfc983d1f3 to your computer and use it in GitHub Desktop.
Path to Sum for Binary Search Trees
const hasPathToSum = function(node, targetSum) {
var sum = 0;
while(sum !== targetSum) {
if (!node) {
break;
}
sum += node.datum;
if (node.datum > targetSum - sum) {
node = node.left;
} else {
node = node.right;
}
}
return sum === targetSum;
};
class BinarySearchTree {
constructor(datum, left = undefined, right = undefined) {
this.datum = datum;
this.left = left;
this.right = right;
}
}
/* ----------------------- example usage ----------------------- */
var bst = new BinarySearchTree(3,
new BinarySearchTree(-1,
new BinarySearchTree(-5),
undefined
),
new BinarySearchTree(5,
new BinarySearchTree(4),
new BinarySearchTree(6))
);
console.log(hasPathToSum(bst, 14));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment