Given a binary tree and a target sum, check whether some root to leaf path adds up to the target. A leaf is a node with no children.
DSA Animator › DSA Revision › Tree › Path Sum
Remember: pass the remaining target down, and check it only at leaves. The or operator stops the search as soon as one path works. The video solves Path Sum (LeetCode 112, Easy) with the DFS with Remaining Target pattern from the Tree topic, and you can replay every step in the interactive Path Sum animation.
Given a binary tree and a target sum, check whether some root to leaf path adds up to the target. A leaf is a node with no children.
In the tree 5, 4, 8, 11, 13, 4, 7, 2, 5, 1, with target 22, the answer is true. The path 5, 4, 11, 2 adds up to 22.
You could list every root to leaf path and sum each one. But we can carry the remaining amount down the tree instead, and never store a path.
Subtract the node value from the target as you go down. At a leaf, check whether the remaining amount is exactly 0. If either subtree returns true, the answer is true. The check must happen only at leaves, because a path has to end at a leaf.
Start with 22, and 5 leaves 17. Going left, 4 leaves 13, and 11 leaves 2. The leaf 7 would leave minus 5, which is not 0, so that path fails. The leaf 2 leaves exactly 0, so this path works. The search returns true right away, without visiting the right side.
In code, return false for a null node. Subtract the value from the target. If the node is a leaf, return whether the target is now 0. Otherwise return the left result or the right result, so it's O of n time.
Remember: pass the remaining target down, and check it only at leaves. The or operator stops the search as soon as one path works.