49: Binary tree path sum

Given a binary tree and a sum. Write a method to check if there's a path from a root to a leaf where a sum of nodes equals to the given sum

 

Example 1

Input:        1    sum = 15
             / \
            2   3
           /   /
          4   5  
             /  
            6 

Output: true

Explanation: path 1->3->5->6

Example 2

Input:     1   sum = 3
          / \  
         5   3 

Output: false