112. Path Sum
Leetcode #: 112
Name: Path Sum
Companies asked: Amazon, Microsoft
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.
The core concept that this problem is testing you on is Backtracking. 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.
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 email@example.com