Educative

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.
What are your thoughts?

  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;
    }

    currentPath.add(node.getValue());
    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

    return total_sums


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