**Explanation**

The idea to this question is to recursively visit each of *root*'s children, if they exist, while decrementing *sum*. Why we decrement sum is because we know the current root-to-leaf-path contains the value *root.val*, so we check if either of *root*'s children contain a root-to-leaf-path of *sum - root.val*.

**Tiem Complexity**

The time complexity is O(n) where n is the size of the tree *root*, since we may visit each node in our tree *root* recursively.

```
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
// Leaf node, check if root.val == sum
else if (root.left == null && root.right == null) {
return root.val == sum;
}
// At least one child is non-null, return their pathSum results
else {
return hasPathSum(root.left, sum - root.val) ||
hasPathSum(root.right, sum - root.val);
}
}
}
```