I have a question in finding the all paths for a sum. The question is:

> 
> Given a binary tree and a number ‘S’, find all paths from root-to-leaf such that the sum of all the node values of each path equals ‘S’.
> 
> 
> 

My approach with recursion is:

```
def all_sum_path(root, target):
    result = []
    find_sum_path(root, target, result, [])
    return result

def find_sum_path(root, target, result, new_path):
    if not root:
        return None
    new_path.append(root.value)
    diff = target - root.value
    if not root.left and not root.right and diff == 0:
        # copy the value of the list rather than a reference
        result.append(list(new_path))
    if root.left:
        return find_sum_path(root.left, diff, result, new_path)
    if root.right:
        return find_sum_path(root.right, diff, result, new_path)
    del new_path[-1]

class TreeNode():
    def __init__(self, _value):
        self.value = _value
        self.left, self.right, self.next = None, None, None

def main():
    root = TreeNode(1)
    root.left = TreeNode(7)
    root.right = TreeNode(9)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(2)
    root.right.right = TreeNode(7)

    print(all_sum_path(root, 12))

    root = TreeNode(12)
    root.left = TreeNode(7)
    root.right = TreeNode(1)
    root.left.left = TreeNode(4)
    root.right.left = TreeNode(10)
    root.right.right = TreeNode(5)

    print(all_sum_path(root, 23))

main()

```

and the output is:

```
[[1, 7, 4]]
[[12, 7, 4]]

Process finished with exit code 0

```

However, the correct approach should be:

```
def all_sum_path(root, target):
    result = []
    find_sum_path(root, target, result, [])
    return result

def find_sum_path(root, target, result, new_path):
    if not root:
        return None
    new_path.append(root.value)
    diff = target - root.value
    if not root.left and not root.right and diff == 0:
        # copy the value of the list rather than a reference
        result.append(list(new_path))
    if root.left:
        find_sum_path(root.left, diff, result, new_path)
    if root.right:
        find_sum_path(root.right, diff, result, new_path)
    del new_path[-1]

class TreeNode():
    def __init__(self, _value):
        self.value = _value
        self.left, self.right, self.next = None, None, None

def main():
    root = TreeNode(1)
    root.left = TreeNode(7)
    root.right = TreeNode(9)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(2)
    root.right.right = TreeNode(7)

    print(all_sum_path(root, 12))

    root = TreeNode(12)
    root.left = TreeNode(7)
    root.right = TreeNode(1)
    root.left.left = TreeNode(4)
    root.right.left = TreeNode(10)
    root.right.right = TreeNode(5)

    print(all_sum_path(root, 23))

main()

```

With output:

```
[[1, 7, 4], [1, 9, 2]]
[[12, 7, 4], [12, 1, 10]]

Process finished with exit code 0

```

I have a some questions here:

1. Why don't we need a `return` in the recursion statement? I am also interested in how the `return` statement reduced the output to only one?
2. Why don't we need the `result = find_sum_path(root, target, result, [])`? Then what is the logic behind to update the results?
3. I am not sure why the time complexity is O(N^2)?

> 
> The time complexity of the above algorithm is O(N^2), where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once (which will take O(N)), and for every leaf node we might have to store its path which will take O(N).
> 
> 
> 

Thanks for your help in advance.