112. 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 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.

Example 1

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

Python

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.

Discord

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

LinkedIn

Portfolio

GitHub

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com