# 112. Path Sum

Leetcode #: 112Name: Path SumDifficulty: EasyCompanies asked: Amazon, MicrosoftUrl:https://leetcode.com/problems/path-sum/

# Prompt

Given the **root** of a binary tree and an integer **targetSum**, your task is to return a boolean value on whether if there exists a **root-to-leaf** path in the tree in which all of the nodes’ values that consist of the path add up to the **targetSum**.

# Approach

The core concept that this problem is testing you on is B**acktracking**. We’ll have to implement a **Backtracking** algorithm using **DFS** (i.e. Depth-First Search) because we essentially have to find a path within the tree (a path starts from the root node and ends on a leaf node).

**Backtracking** is a strategy that allows you to retract from exploring a path to its absolute depth depending on some sort of condition or constraint. In this case, the condition that we want to check is if our **root-to-leaf **path adds up to the **targetSum**. In other words, in this case, if the path that we discover within the tree consists of node values that when added up doesn’t equal to the **targetSum**, then we can retract or **backtrack** our current path and instead explore a new path within the tree until we discover one whose node values added together equals to the **targetSum**.

If we have a look at the binary tree above which also can be found as example 1 in the direct url of the problem on LeetCode, our DFS algorithm will scan this binary tree from left to right. The first path that we’d discover would be [5, 4, 11, 7] which sums up to 27 and let’s say that the targetSum is 22, then this path would not have satisfied the problem so we’d return False. By returning False, we would **backtrack** from the leaf node with a value of 7 to the node with a value of 11 and then explore the other leaf node with a value of 2 in the left subtree of the root node. In this case, the path generated would be [5, 4, 11, 2] which in fact sums up to 22 and equals to the targetSum. Because of this reason, we can return True which would bubble up back to the root node in which we can then return True from the top most level call of the function.

# Code

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com