# Solution

• Approach #1 (Pre-order Traversal) [Accepted]

The points needed to solve this problem include: 1) we need to know if a node is a "leaf" or not. 2) We need to include the prefixes before the "leaves". From the pre-order traversal we could get the result. So basically, this is a tree traversal problem. The implementation in Python.

``````class Solution(object):
def binaryTreePaths(self, root):
results =[]
prefixes = ""
def preOrderTraversal(predix,root):
if root is not None:
prefixes +="->"+str(root.val) if predix else str(root.val)
preOrderTraversal(prefixes ,root.left)
preOrderTraversal(prefixes ,root.right)
if root.left is None and root.right is None:
results.append(prefixes )
preOrderTraversal(predix,root)
return results
``````

Complexity Analysis:
Time complexity : O(n). This is the time complexity of doing pre-order traversal. Since in-order, pre-order and post-order traversals are Depth-first traversals, they complexity is O(n+m), m is the number of edges. In a binary tree, the maximum number of edges is n-1. Thus the time complexity is O(n+n-1), which is O(n).
Space complexity : O(n*log(n)). The space saved in the results is decided by the number of leaves (n/2), and each one takes the height of the tree(log(n)) as maximum space.

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