**Solution**

**Binary Tree Paths** https://leetcode.com/problems/binary-tree-paths/

**Standard Pre-Order Traversal**

- Keep a list so_far to track the path so_far
- Use the standard backtracking template to enumerate all paths
- Time Complexity: We traverse every node just once. For every leaf, we copy the path so_far into result list. Say there are L leaves and average lenght of each path is K. Then the complexity is O(LK). For a balanced tree, L ~ N (N//2) and K is ~Lg(N), so we have O(N * lg(N)). For a general worst case, we have O(N^2).
- Space Complexity: O(N).

```
class Solution:
# @param {TreeNode} root
# @return {string[]}
def binaryTreePaths(self, root):
result = []
if root:
self.helper(root, [], result)
return result
def helper(self, root, so_far, result):
if root.left is None and root.right is None:
so_far.append(root.val)
result.append("->".join(map(str, so_far)))
so_far.pop()
else:
so_far.append(root.val)
if root.right:
self.helper(root.right, so_far, result)
if root.left:
self.helper(root.left, so_far, result)
so_far.pop()
return
```