Binary Tree Paths

Problem Summary

• Given a tree, return each path from root to leaf node

Main Concepts Used

• Trees
• Breadth First Search
• Backtracking

Time & Space Complexity

• Time: $O(n)$ → Reason: Visiting each node
• Space: $O(n)$ → Reason: Storing each node

Code

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        result = []
        current = []

        def bfs(root):
            if not root.left and not root.right:
                current.append(str(root.val))
                result.append("->".join(current))
                return

            current.append(str(root.val))
            if root.left:
                bfs(root.left)
                current.pop()
            if root.right:
                bfs(root.right)
                current.pop()

        bfs(root)
        return result