Iterative O(N) Python Solution
Intuition\n\nThe key to a linear solution is the realization that...\n\nIf at a given node, the sum of all the nodes from the current node to root subtracted by
# Intuition\n\nThe key to a linear solution is the realization that...\n\n**If at a given node, the sum of all the nodes from the current node to root subtracted by k is equal to a sum to the root that was observed previously on this path, then there are paths that sum to k equal to the number of times `sumToRoot - k` was previously encountered.**\n\nExample:\n```\n# Input: A tree that is one long line of left children.\n\nroot: [10, 3, null, 5, null, -5, null, 5, null 0]\nk: 8\n```\n\nThe sums-to-root, or prefix sum as it is more commonly called are as we travel down the leftmost path.\n\n`[10, 13, 18, 13, 18, 18]`\n\nObserve that at as we visit index i where i is equal to 5, 5, and 0, we encounter a prefix sum of `18`.\n\nif `prefixSum - k == previouslySeenPrefixSum` then we know that we can count a path that sums to k for each time that sum was previously observed.\n\n`0 + 0 + 1 + 0 + 1 + 1 = 3`\n\nIf we remove previously observed sums from a dictionary that keeps track of their counts as previously considered nodes are no longer a part of the current path we are evaluating, then we can use this logic for more complex trees as well.\n\n\n# Approach\nTraverse the tree once in "preorder" order. As we visit nodes keep a stack of nodes to visit next, always making sure that the next left child is last on the stack.\n\nAs we go, track the sum of all nodes, and a stack of those node values. If the next node that we should check is at a depth that is more shallow than the number of nodes that currently make up the prefix sum, remove values until the prefix sum is equal to the current path to the root.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\nEvery node is visited once.\n\nEvery node value is added to the stack of currently used nodes once. Every node is removed from that node once.\n\nChecks made to see if `prefixSum - k` was encountered previously as a prefix sum (and how many times) are made against a dictionary in constant time.\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution:\n    def pathSum(self, root: TreeNode, k: int) -> int:\n\n        if root is None:\n            return 0\n        \n        # Track whenever we discover a path that sums to k\n        count = 0\n\n        # Track the sum of all the nodes that we have seen thus far while traversing this path.\n        # If we backtrack, we will remove a count to represent it not being a part of the current path we are evaluating.\n        prefixSums = collections.defaultdict(int)\n        \n        # Keep track of the most recently added values to prefixSum.\n        # When we leave a path and traverse down a neihboring path, \n        # this allows us to efficiently correct the prefixSum up until that point.\n        prefixNodes = []\n        prefixSum = 0\n\n        # Track the next nodes to evaluate such that the next preorder node is always the last element.\n        nextNodes = [(root, 1)]\n        \n        while nextNodes:\n            \n            node, depth = nextNodes.pop()\n\n            # This block here performs the "recursion magic"\n            # of the provided editorial solution explicitly.\n            # Correct the prefixSum by subtracting the values of \n            # nodes that are not a part of the this node\'s path to the root.\n            while len(prefixNodes) >= depth:\n                prefixSums[prefixSum] -= 1\n                prefixSum -= prefixNodes.pop()\n\n            prefixSum += node.val\n            \n            # The current path from the root sums to k.\n            if prefixSum == k:\n                count += 1\n\n            # The prefixSums dictionary tracks all of the sums that we have seen to the root. \n            # If there exists a sum in there that is the k subtracted from the current path to the root, \n            # then the nodes we have added between then and now sum to k.\n            count += prefixSums[prefixSum - k]\n\n            prefixNodes.append(node.val)\n            prefixSums[prefixSum] += 1 \n\n            # Add additional child nodes such that the left most node gets popped next.\n            if node.right:\n                nextNodes.append((node.right, depth + 1))\n\n            if node.left:\n                nextNodes.append((node.left, depth + 1))\n\n        return count\n\n\n\n\n```
['Python3']