//given a BST with integer node values, find the path to a target sum.
//Assumptions:
//Inputs: a start node and a target value
//Outputs: boolean
//Methodology: since negative numbers change things, A full tree traversal is required.
//I will go with depth first since this will be easier to trace routes

class Node {
  constructor(value) {
    //the node value (integers only here)
    this.value = value;
    //left and right are references to other nodes
    //left = lt, right = gt
    this.left = null;
    this.right = null;
  }
  addChild(value) {
    //add a child to the tree
    if (value < this.value) {
      if (this.left) {
        this.left.addChild(value);
      }
      else {
        this.left = new Node(value);
      }
    }
    else if (value > this.value) {
      if (this.right) {
        this.right.addChild(value);
      }
      else {
        this.right = new Node(value);
      }
    }
  }
}

const hasPathToSum = (node, targetSum) => {
  targetSum -= node.value;
  if (targetSum === 0) return true;
  if (node.left) {
    let result = hasPathToSum(node.left, targetSum);
    if (result) {
      return true;
    }
  }
  if (node.right) {
    let result = hasPathToSum(node.right, targetSum);
    if (result) {
      return true;
    }
  }
  return false; //If we made it here, there was no path to the target sum();
};

//test
//one
//      10
//    6    12
//  3   9 11   13


// let treeOne = new Node(10);
// treeOne.addChild(6);
// treeOne.addChild(12);
// treeOne.addChild(3);
// treeOne.addChild(9);
// treeOne.addChild(11);
// treeOne.addChild(13);
// console.log('testing tree one');
// console.log(hasPathToSum(treeOne, 35)); //true
// console.log(hasPathToSum(treeOne, 19)); //true
// console.log(hasPathToSum(treeOne, 25)); //true
// console.log(hasPathToSum(treeOne, 22)); //true
// console.log(hasPathToSum(treeOne, 16)); //true
// console.log(hasPathToSum(treeOne, 33)); //true
// console.log(hasPathToSum(treeOne, 10)); //true
// console.log(hasPathToSum(treeOne, 21)); //false
// console.log(hasPathToSum(treeOne, -10)); //false
// console.log(hasPathToSum(treeOne, 100)); //false
// console.log(hasPathToSum(treeOne, 0)); //false
// console.log();


//test
//two
//           20
//        10    30
//     -9   15 25   40
// -100 -5

// let treeTwo = new Node(20);
// treeTwo.addChild(10);
// treeTwo.addChild(30);
// treeTwo.addChild(-9);
// treeTwo.addChild(15);
// treeTwo.addChild(25);
// treeTwo.addChild(40);
// treeTwo.addChild(-100);
// treeTwo.addChild(-5);
// console.log('testing tree two');
// console.log(hasPathToSum(treeTwo, 20)); //true
// console.log(hasPathToSum(treeTwo, 50)); //true
// console.log(hasPathToSum(treeTwo, 90)); //true
// console.log(hasPathToSum(treeTwo, 75)); //true
// console.log(hasPathToSum(treeTwo, 30)); //true
// console.log(hasPathToSum(treeTwo, 45)); //true
// console.log(hasPathToSum(treeTwo, 21)); //true
// console.log(hasPathToSum(treeTwo, 16)); //true
// console.log(hasPathToSum(treeTwo, -79)); //true
// console.log(hasPathToSum(treeTwo, -100)); //false
// console.log(hasPathToSum(treeTwo, 100)); //false
// console.log(hasPathToSum(treeTwo, 0)); //false


//all tests pass