title: Find maximum sum path through binary tree - javascript
body: <p>I've been trying to figure this problem out for a couple days and can't seem to optimize the solution to make it tenable. </p>
  
  <p>I have a tree that's 100 levels deep, so brute force (2^100 possible combinations?) is obviously not working.. </p>
  
  <p>Here is the code I have so far: </p>
  
  <pre><code>// Node constructor | structure of nodes
  var Node = function(val) {
    this.val = Number(val);
    this.left = null;
    this.right = null;
  }
  
  function maxPathUtil(top, store) {
    if (top === null || top === undefined) return 0;
    if (top.left === null &amp;&amp; top.right === null) {
      // console.log("hello");
      return top.val;
    }
  
    leftSub = maxPathUtil(top.left, store);
    rightSub = maxPathUtil(top.right, store);
    store[0] = Math.max(store[0], leftSub+rightSub+top.val);
  
    return Math.max(leftSub, rightSub) + top.val;
  }
  
  function maxPathSum(top) {
    store = [];
    store[0] = 0;
    maxPathUtil(top, store)
    return store[0];
  }
  
  var top = nodify(levels);
  console.log(maxPathSum(top));
  </code></pre>
  
  <p>Is there a way to memoize this solution / otherwise improve the big O or is that as efficient as it gets?</p>