if i use recursion to solve the problem, what is the space complexity, O(n) or O(logn)?

Code:

```
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
if not root.left and not root.right:
return root.val == sum
return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
```