path-sum-ii.py

#  https://leetcode.com/problems/path-sum-ii/
#  Related Topics: Tree, DFS
#  Difficulty: Medium


# Initial thoughts:
# Using a DFS algorithm we are going to check every path from root to its leafs
# and subtracts the the nodes values from the given sum. If at the end sum turns
# out to be zero, we have a path with the given sum.
# One thing to be aware of is that we need to check that we are at a leaf. The condition
# for that is that both its left and right children are null. It is not enough to check that
# the node itself is null because the null node could be the child from a parent node that
# has its other child not null (in any case the definition of a leaf IS that both its children must be nulls)
# Now, to return all the valid paths we need to save them in a temporary solution variable that we pass along
# and push that to a result variable that will hold all the solutions.
# Keeping track of the result variable is easy but tracking the solution variable has two option:
# We either copy the solution array each time we call the function recursively (which will badly increase our
# Space Complexity) or we can simulate the stack by pushing the current nodes variable to the back of it
# and then popping it when the recursion returns.
# But there is a catch: Since arrays are reference values, we need to copy (deep copy) the solution array to
# the result array if it turns out to be a correct solution, otherwise, it will be the same array whose values
# will be popped out one by one when the recursive functions return and we end up with an empty solution.

# Time complexity: O(n) where n === the number of nodes in the tree
# Space complexity: O(depth * 2^depth) this auxilliary space is needed for the result variable. Consider a worst
# case scenario where we deal with a fully ballanced tree where every path is a solution. In this case the number
# of our solutions will equal the number of leaf nodes which are 2^depth of the tree and each solution will hold
# a number of nodes equal to the depth of the tree.

# Definition for a binary tree node.
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        results = []
        self.traverse(root, sum, [], results)
        return results

    def traverse(self, root: TreeNode, sum: int, solution: List[int], results: List[List[int]]):
        if root == None:
            return
        solution.append(root.val)
        if root.left == None and root.right == None and sum - root.val == 0:
            results.append(list(solution))
        self.traverse(root.left, sum - root.val, solution, results)
        self.traverse(root.right, sum - root.val, solution, results)
        solution.pop()