Sign in
Skip to solution
easyDSA

How do you check if a root-to-leaf path sums to a target?

609 views
01

Understand the problem

Explain path sum.

treesrecursion
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Recurse, subtracting each node's value from the target. At a leaf, success means the remaining target equals the leaf's value (i.e. reaches 0). Explore left or right; any successful branch returns true. O(n).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

DFS subtracting the target
Run Playground
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:    # leaf
        return target == root.val
    rest = target - root.val
    return has_path_sum(root.left, rest) or has_path_sum(root.right, rest)


# --- demo ---
root = TreeNode(5, TreeNode(4, TreeNode(11)), TreeNode(8))
print(has_path_sum(root, 20))   # True   (5 -> 4 -> 11)
print(has_path_sum(root, 21))   # False
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 16 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track