Root to leaf path sum

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Check if there exists a root-to-leaf path with sum equal to target.

Algorithm

1DFS: subtract node value from target. At leaf: check if target == 0.

Common Pitfalls

•Same as LC 112. Recurse with remaining sum. Leaf condition: no children. O(n).

Root to leaf path sum.java

Java

// Approach: DFS. Track current path sum; at leaf, check if it equals target.
// Time: O(n) Space: O(h)
class Solution {
    boolean hasPathSum(Node root, int target) {
        return pathSum(root, target);
    }

    boolean pathSum(Node root, int target) {
        if (root == null)
            return false;

        if (root.left == null && root.right == null)
            return root.data == target;

        boolean left = pathSum(root.left, target - root.data);
        boolean right = pathSum(root.right, target - root.data);

        return left || right;
    }
}

class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

Was this solution helpful?