educative.io

O(1) Memory with Same time

Courses
,
#1 
def count_paths(root, S):

    return count_paths_helper(root, S)


def count_paths_helper(root, S):

    if root is None:  # undefined null node
        return 0

    if root.val == S:  # if current node = S and no children nodes used
        return 1

    # cases where we use children nodes
    path_sum = 0
    for target_sum in [S, S - root.val]:
        path_sum += count_paths_helper(root.left, target_sum)
        path_sum += count_paths_helper(root.right, target_sum)

    return path_sum

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5658962204557312

#2

The space complexity of the above algorithm will be O(N). This space will be used to store the recursion stack. You are using recursion in your algo then how do you define it in O(1)?

1 Like
#3

It is neither O(1) or O(n), if the tree is balanced it’s O(n^2) and if not then it’s worse.

Also I’m not sure his code is correct, he talks about cases where children are or aren’t used but doesn’t enforce that in code. His code seems wrong.

@Akshay_Goel can you please double check your code is right? Have you tested it? Can you explain how you’re taking the correct action based on whether or not child nodes are used?

#4

Yes, you are right. I completely missed that aspect. It should be O(N). It’s essentially a DFS.

#5

I think it’s O(n) if the tree is balanced as it’s a DFS traversal.

Looking back on this, I agree the logic is confusing. I’ll revisit it soon if I have time! If you find any examples that break this please do share!

#6

@Basil_Al_Masri

So I found a working solution on LeetCode discussion and mine definitely seems wrong now. I can keep this thread around in case anyone is interested in seeing the discussion!

The idea here seems to be to constantly build all possible targets for valid paths and push these down in a DFS traversal.

We count all the times we can achieve this at the leaves using count = targets.count(node.val)

class Solution(object):
    def pathSum(self, root, s):
        return self.dfs(root, s, [s])

    def dfs(self, node, origin, targets):
        if not node:
            return 0
        count = targets.count(node.val)
        targets = [origin] + [
            t - node.val for t in targets
        ]  # update the targets
        return (
            count
            + self.dfs(node.left, origin, targets)
            + self.dfs(node.right, origin, targets)
        )