Trees : Path Sum II

(Medium)

Leetcode link : https://leetcode.com/problems/path-sum-ii/submissions/

Medium

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

Solution:

Based on the same solution logic as https://takeitoutamber.medium.com/bst-sum-root-to-leaf-numbers-a8f64e3d9ba1

Approach: Depth First Traversal | Recursion

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res = []
        
        # stack will be used for tracing the tree in order, 
        # array [] will be used to keep track of the current stack trace from root to leaf
        stack = [(root, [])]
        
        while stack:
            node, current_stack = stack.pop()
            
            if node:
                current_stack.append(node.val)
                if not node.left and not node.right:
                    if self.sum_array(current_stack) == sum:
                        res.append(current_stack)
                        current_stack = []
                else:
                    stack.append((node.right, copy.deepcopy(current_stack)))
                    stack.append((node.left, copy.deepcopy(current_stack)))
                    
                    
        return res
    
    def sum_array(self, arr: List[int]) -> int:
        tot = 0
        for x in arr:
            tot += x
        return tot

Success :

Runtime: 536 ms, faster than 5.06% of Python3 online submissions forPath Sum II.

Memory Usage: 19.2 MB, less than 31.04% of Python3 online submissions for Path Sum II.

Complexity Analysis

• Time Complexity: O(N-square) where N are the number of nodes in a tree. In the worst case, we could have a complete binary tree and if that is the case, then there would be N/2 leafs. For every leaf, we perform a potential O(N) operation of copying over the pathNodes(current_stack)nodes to a new list to be added to the final pathsList. Hence, the complexity in the worst case could be O(N-square).
• Space Complexity: O(N). The space complexity, like many other problems is debatable here. I personally choose not to consider the space occupied by the output in the space complexity. So, all the new lists that we create for the paths are actually a part of the output and hence, don't count towards the final space complexity. The only additional space that we use is the pathNodes list to keep track of nodes along a branch.
• We could include the space occupied by the new lists (and hence the output) in the space complexity and in that case the space would be O(N-square). There’s a great answer on Stack Overflow about whether to consider input and output space in the space complexity or not. I prefer not to include them.