In this post I'll go over how to approach a binary tree problem using the depth first search recursive method. I will be using an example, so if you don't want any spoilers on how to solve the problem, I will list the problem now. The problem is:

• Path Sum II || MEDIUM

Let's go over Path Sum II. In this problem, we are given a binary tree, and we are asked to return all root to leaf paths that sum to a given value called targetSum. A leaf is defined as a node with no children(left or right nodes). Think about this problem for a little. How can we solve it?

Now that you've had some time to think about it, I'll go over the solution. Let's say we know how to keep track of the paths already. What should happen when we reach a leaf node? How should we identify when we reach a leaf node? Well, a leaf node is a node with no children, so we have to check if node.right is None and node.left is None. When we see that, we have to check the sum of our path, and see if it is equal to targetSum, and if so, we add the path to some ans variable. But... that is not very efficient. The optimal way to do this is during our searching function, we subtract our current node's value from the targetSum. Now, if we see a leaf node, all we have to do is check our targetSum. If it is 0, we have found a path.

Now that we know how to check for a valid path, how do we find these paths? Well, we have to use backtracking, where we search down one path and if it is incorrect, you backtrack to your starting position and go down another path. The recursive part is simple. In our search function, we take the target, node, and current path. We add our value to the path, and then call search(node.left, target, path). After these two calls, we call path.pop() to remove the last move(as if it was a valid path, it will have been appended to ans).

Now let me show you the code for a better understanding of how things work here. The code is written in python, but it shouldn't be hard for you to figure out what the code is doing, because python is easy to read mostly.

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        def dfs(root, target, path):
			# check if we are at a null node || base case
            if root is None: return None
			# subtract cur node's value from target & append to path
            target -= root.val
            path.append(root.val)
			# check if value is a leaf node and check if path sums to target
            if root.left is None and root.right is None and target == 0:
                ans.append(path.copy())
            else:
				# search left and right node
                dfs(root.left, target, path)
                dfs(root.right, target, path)
			# backtrack
            path.pop()
            
		# startup code
        ans = []
        dfs(root, targetSum, [])
        return ans

⬆️ Please upvote if this helped! ⬆️