Time complexity of returning every path in a binary tree whose path equals the target sum-CodePudding

I solved LeetCode challenge 113. Path Sum II:

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

This is my code:

var pathSum = function(root, targetSum) {
    let paths = [];
    if(root === null) {
        return [];
    }
    getAllSumPaths(root, [], paths, targetSum);
    return paths;
}; 

function getAllSumPaths(root, currPath, paths, targetSum) {
    if(root.left === null && root.right === null) {
        if(targetSum - root.val === 0) {
            currPath.push(root.val);
            paths.push([...currPath]);
            currPath.pop();
        }
        return;
    }
    currPath.push(root.val);
    if(root.left !== null){
        getAllSumPaths(root.left, currPath, paths, targetSum - root.val);
    }
    if(root.right !== null){
        getAllSumPaths(root.right, currPath, paths, targetSum - root.val);        
    }
    currPath.pop();
}

Initially I figured the time complexity would just be O(n) where n is the number of nodes in the tree. However, while writing this, I had to use the spread operator to create a new instance of a valid path to add to my paths array by doing paths.push([...currPath]); because the subsequent pop() calls would modify the paths already pushed and I would get empty paths in the end.

But I found that the spread operation has an O(n) time complexity where n would be the size of the path. I'm not sure how that factors into the time complexity of the algorithm. Any ideas? and is there another way to write this so I don't have an O(n) operation when I find a valid path?

CodePudding user response：

I had to use the spread operator to create a new instance of a valid path to add to my paths array by doing paths.push([...currPath])

Yes, this is needed, as otherwise you only have one path that keeps on mutating.

the spread operation has an O(n) time complexity where n would be the size of the path. I'm not sure how that factors into the time complexity of the algorithm.

You are right that the