Tree Path to Target Sum - HR Interview Prep

gistfile1.txt

const hasPathToSum = function(node, targetSum) {
  
  let hasSum = (sum, node) => {
    sum += node.value;
    if (node.children.length === 0) {
      if (sum === targetSum) {
        return true;
      } else {
        return false;
      }
    } else {
      for (let i = 0; i < node.children.length; i++) {
        if (hasSum(sum, node.children[i])) {
          return true;
        }
      }
      return false;
    }
  };
  
  return hasSum(0, node);
};

class Tree {
  constructor (value) {
    this.value = value;
    this.children = [];
  }
  
  addChild (tree) {
    this.children.push(tree);
    if (this.children.length > 2) {
      throw 'Too many children!';
    }
  }
}

class TestSuite {
  constructor() {
    this.passCount = 0;
    this.failCount = 0;
  }
  
  runTests () {
    let root = new Tree(5);
    this.assert(hasPathToSum(root, 5), true, 'Should return true for tree\'s value when it has no children');
    root.addChild(new Tree(4));
    this.assert(hasPathToSum(root, 9), true, 'Should return true for total value of tree with one child');
    this.assert(hasPathToSum(root, 5), false, 'Should only return true for values that end on leaves');
    root.addChild(new Tree(2));
    this.assert(hasPathToSum(root, 9), true, 'Should return true for both leaves when tree has multiple children');
    this.assert(hasPathToSum(root, 7), true, 'Should return true for both leaves when tree has multiple children');
    root.children[0].addChild(new Tree(8));
    this.assert(hasPathToSum(root, 17), true, 'Should be able to check sums of deeply nested children');
    
    this.printTestReport();
  }
  
  assert (val1, val2, testname) {
    if (val1 === val2) {
      this.passCount++;
    } else {
      console.error('Test failed: ' + testname);
      this.failCount++;
    }
  }
  
  printTestReport () {
    if (this.failCount === 0 && this.passCount === 0) {
      console.log('No tests were run');
    } else if (this.failCount > 0) {
      console.log('Passed ' + this.passCount + ' tests');
      console.error('Failed ' + this.failCount + ' tests');
    } else {
      console.log('Passed all ' + this.passCount + ' tests');
    }
  }
}


new TestSuite().runTests();