# Python Solution with Detailed Explanation

• 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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.