# Anther approach could be to use sliding window for path sum

Hi guys,

Instead of calculating pathSum on every node. Another approach could be to use a sliding window for maintaining path sum. I believe time complexity will be improved to O(N log N).

O(N) for traversing the tree.
For the sliding window, all paths will be accessed once. So total paths( (N+1) / 2) * height of balanced Tree (log N) elements will be accessed.
O((N+1) / 2 * log N) => O(N log N)

O(N) + O (N log N) => O (N log N) should be the time complexity.

``````  private static int findPaths(TreeNode root, int reqSum) {
List<Integer> currentPath = new ArrayList<>();
return findPathRecursively(root, currentPath, 0, reqSum, 0);
}

private static int findPathRecursively(
TreeNode node,
List<Integer> currentPath,
int prevSum,
int reqSum,
int begIndex
) {
if (node == null) {
return 0;
}

int currSum = prevSum + node.getValue();
int matchedPaths = 0;

while (currSum >= reqSum) {
if (currSum == reqSum) {
matchedPaths++;
}

currSum -= currentPath.get(begIndex);
begIndex++;
}

int leftMatchedPaths = findPathRecursively(node.getLeftNode(), currentPath, currSum, reqSum,
begIndex);
int rightMatchedPaths = findPathRecursively(node.getRightNode(), currentPath, currSum, reqSum,
begIndex);

currentPath.remove(currentPath.size() - 1);
return leftMatchedPaths + rightMatchedPaths + matchedPaths;
}
``````

Thanks

This is the solution I thought of as well. However, I think the time complexity is still O(n^2) as in the worst case (tree is a linkedlist - every node except the leaf has a single child) the depth of the tree is N and the root-to-leaf path is therefore N too.

I do think this is a more elegant approach. I implemented it in python:

EDIT: Note that I am no expert though! There may be something wrong in my solution. I do think I need an extra case in the while loop to account for zeros. When you have zeros, multiple paths can be found through the same nodes to reach the sum.

``````import collections

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

def count_paths(root, S):
total_sums = 0
for path in iter_all_paths_dfs(root):
end_index = 0
start_index = 0
running_sum = 0
while end_index < len(path):
running_sum += path[end_index]
while running_sum > S and start_index < end_index:
running_sum -= path[start_index]
start_index += 1

if running_sum == S:
total_sums += 1

end_index += 1

def iter_all_paths_dfs(node, current_path=collections.deque()):

if node is None:
return

current_path.append(node.val)

if not node.left and not node.right:
# Leaf node.
yield list(current_path)

yield from iter_all_paths_dfs(node.left)
yield from iter_all_paths_dfs(node.right)

current_path.pop()
``````
1 Like