'''
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’.
Time complexity #
The time complexity of the above algorithm is O(N^2)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)O(N)), and for every leaf node we might have to store its path which will take O(N)O(N).

We can calculate a tighter time complexity of O(NlogN)O(NlogN) from the space complexity discussion below.

Space complexity #
If we ignore the space required for the allPaths list, the space complexity of the above algorithm will be O(N)O(N) in the worst case. This space will be used to store the recursion stack. The worst case will happen when the given tree is a linked list (i.e., every node has only one child).

How can we estimate the space used for the allPaths array? Take the example of the following balanced tree:
'''
class TreeNode:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right


def find_paths(root, required_sum):
  allPaths = []
  find_paths_recursive(root, required_sum, [], allPaths)
  return allPaths


def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
  if currentNode is None:
    return

  # add the current node to the path
  currentPath.append(currentNode.val)

  # if the current node is a leaf and its value is equal to required_sum, save the current path
  if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
    allPaths.append(list(currentPath))
  else:
    # traverse the left sub-tree
    find_paths_recursive(currentNode.left, required_sum -
                         currentNode.val, currentPath, allPaths)
    # traverse the right sub-tree
    find_paths_recursive(currentNode.right, required_sum -
                         currentNode.val, currentPath, allPaths)

  # remove the current node from the path to backtrack,
  # we need to remove the current node while we are going up the recursive call stack.
  del currentPath[-1]


def main():

  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)
  required_sum = 23
  print("Tree paths with required_sum " + str(required_sum) +
        ": " + str(find_paths(root, required_sum)))


main()

c5bd07fb507f74c40e5fafb38cb9d8c877bc22a6
<mask token>


class TreeNode:

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


<mask token>


def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
    if currentNode is None:
        return
    currentPath.append(currentNode.val)
    if (currentNode.val == required_sum and currentNode.left is None and 
        currentNode.right is None):
        allPaths.append(list(currentPath))
    else:
        find_paths_recursive(currentNode.left, required_sum - currentNode.
            val, currentPath, allPaths)
        find_paths_recursive(currentNode.right, required_sum - currentNode.
            val, currentPath, allPaths)
    del currentPath[-1]


<mask token>

<mask token>


class TreeNode:

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


def find_paths(root, required_sum):
    allPaths = []
    find_paths_recursive(root, required_sum, [], allPaths)
    return allPaths


def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
    if currentNode is None:
        return
    currentPath.append(currentNode.val)
    if (currentNode.val == required_sum and currentNode.left is None and 
        currentNode.right is None):
        allPaths.append(list(currentPath))
    else:
        find_paths_recursive(currentNode.left, required_sum - currentNode.
            val, currentPath, allPaths)
        find_paths_recursive(currentNode.right, required_sum - currentNode.
            val, currentPath, allPaths)
    del currentPath[-1]


<mask token>

<mask token>


class TreeNode:

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


def find_paths(root, required_sum):
    allPaths = []
    find_paths_recursive(root, required_sum, [], allPaths)
    return allPaths


def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
    if currentNode is None:
        return
    currentPath.append(currentNode.val)
    if (currentNode.val == required_sum and currentNode.left is None and 
        currentNode.right is None):
        allPaths.append(list(currentPath))
    else:
        find_paths_recursive(currentNode.left, required_sum - currentNode.
            val, currentPath, allPaths)
        find_paths_recursive(currentNode.right, required_sum - currentNode.
            val, currentPath, allPaths)
    del currentPath[-1]


def main():
    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)
    required_sum = 23
    print('Tree paths with required_sum ' + str(required_sum) + ': ' + str(
        find_paths(root, required_sum)))


<mask token>

<mask token>


class TreeNode:

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


def find_paths(root, required_sum):
    allPaths = []
    find_paths_recursive(root, required_sum, [], allPaths)
    return allPaths


def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
    if currentNode is None:
        return
    currentPath.append(currentNode.val)
    if (currentNode.val == required_sum and currentNode.left is None and 
        currentNode.right is None):
        allPaths.append(list(currentPath))
    else:
        find_paths_recursive(currentNode.left, required_sum - currentNode.
            val, currentPath, allPaths)
        find_paths_recursive(currentNode.right, required_sum - currentNode.
            val, currentPath, allPaths)
    del currentPath[-1]


def main():
    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)
    required_sum = 23
    print('Tree paths with required_sum ' + str(required_sum) + ': ' + str(
        find_paths(root, required_sum)))


main()

'''
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’.
Time complexity #
The time complexity of the above algorithm is O(N^2)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)O(N)), and for every leaf node we might have to store its path which will take O(N)O(N).

We can calculate a tighter time complexity of O(NlogN)O(NlogN) from the space complexity discussion below.

Space complexity #
If we ignore the space required for the allPaths list, the space complexity of the above algorithm will be O(N)O(N) in the worst case. This space will be used to store the recursion stack. The worst case will happen when the given tree is a linked list (i.e., every node has only one child).

How can we estimate the space used for the allPaths array? Take the example of the following balanced tree:
'''
class TreeNode:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right


def find_paths(root, required_sum):
  allPaths = []
  find_paths_recursive(root, required_sum, [], allPaths)
  return allPaths


def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
  if currentNode is None:
    return

  # add the current node to the path
  currentPath.append(currentNode.val)

  # if the current node is a leaf and its value is equal to required_sum, save the current path
  if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
    allPaths.append(list(currentPath))
  else:
    # traverse the left sub-tree
    find_paths_recursive(currentNode.left, required_sum -
                         currentNode.val, currentPath, allPaths)
    # traverse the right sub-tree
    find_paths_recursive(currentNode.right, required_sum -
                         currentNode.val, currentPath, allPaths)

  # remove the current node from the path to backtrack,
  # we need to remove the current node while we are going up the recursive call stack.
  del currentPath[-1]


def main():

  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)
  required_sum = 23
  print("Tree paths with required_sum " + str(required_sum) +
        ": " + str(find_paths(root, required_sum)))


main()
