# Java O(n) Easy To Understand, Optimal Solution

• 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);
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.