class Solution(object):
    def binaryTreePaths(self, root):
        if not root: return []
        
        arrow = '->'

        ans = []
        stack = []
        stack.append((root, ''))

        while stack:
            node, path = stack.pop()
            path += arrow+str(node.val) if path else str(node.val) #add arrow except beginnings
            if not node.left and not node.right: ans.append(path) #if isLeaf, append path.
            if node.left: stack.append((node.left, path))
            if node.right: stack.append((node.right, path))

        return ans


"""
Time: O(N)
Space: O(N)

Standard BFS.
"""
class Solution(object):
    def binaryTreePaths(self, root):
        q = collections.deque([(root, '')])
        ans = []
        
        while q:
            node, path = q.popleft()
            
            path = (path+'->'+str(node.val)) if path else str(node.val)
            
            if node.left: q.append((node.left, path))
            if node.right: q.append((node.right, path))

            if not node.left and not node.right: ans.append(path)
            
        return ans
class Solution(object):
    def binaryTreePaths(self, root):
        if not root: return []
        
        arrow = '->'

        ans = []
        stack = []
        stack.append((root, ''))

        while stack:
            node, path = stack.pop()
            path += arrow+str(node.val) if path else str(node.val) #add arrow except beginnings
            if not node.left and not node.right: ans.append(path) #if isLeaf, append path.
            if node.left: stack.append((node.left, path))
            if node.right: stack.append((node.right, path))

        return ans


"""
Time: O(N)
Space: O(N)

Standard BFS.
"""
class Solution(object):
    def binaryTreePaths(self, root):
        q = collections.deque([(root, '')])
        ans = []
        
        while q:
            node, path = q.popleft()
            
            path = (path+'->'+str(node.val)) if path else str(node.val)
            
            if node.left: q.append((node.left, path))
            if node.right: q.append((node.right, path))

            if not node.left and not node.right: ans.append(path)
            
        return ans
#add arrow except beginnings #if isLeaf, append path. Time: O(N) Space: O(N)  Standard BFS.