257. Binary Tree Paths

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Recursive DFS	Traverse tree recursively, building path by adding nodes and backtracking. When reaching leaf, add complete path to result. Uses implicit call stack.	\(O(N)\)	\(O(N)\)
Iterative DFS	Use explicit stack to store (node, path_string) pairs. Build path strings as we traverse. When reaching leaf, add path to result. No backtracking needed.	\(O(N)\)	\(O(N)\)

Implementation

PythonJavaScriptGo

Recursive DFS

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

        result: List[str] = []
        path: List[str] = []

        def dfs(node: TreeNode, path: List[str]) -> None:
            path.append(str(node.val))

            if node.left == None and node.right == None:
                result.append("->".join(path))

            if node.left:
                dfs(node.left, path)

            if node.right:
                dfs(node.right, path)

            path.pop()

        dfs(root, path)
        return result

Iterative DFS

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

        stack: List[Tuple[TreeNode, str]] = []
        stack.append(
            (root, str(root.val))
        )
        while stack:
            node, path = stack.pop()
            if node.left == None and node.right == None:
                result.append(path)
            if node.left:
                stack.append(
                    (node.left, path + "->" + str(node.left.val))
                )
            if node.right:
                stack.append(
                    (node.right, path + "->" + str(node.right.val))
                )
        return result