Binary Tree Paths - Leetcode Solution

Problem: Given the root of a binary tree, return all root-to-leaf paths in any order.

Example:

Input: [1,2,3,null,5] Output: ["1->2->5","1->3"]

Explanation: The paths are:

1. 1 -> 2 -> 5
2. 1 -> 3

Solution: To solve this problem, we can use a recursive approach. We traverse the tree in a DFS (Depth First Search) manner starting from the root node. We also keep track of the current path using a list of integers.

We visit each node and add it to the current path. If we reach a leaf node (i.e., a node with no children), we add the current path to the result list. Otherwise, we recursively traverse the left and right subtrees.

At each step of the traversal, we backtrack by removing the last node from the current path so that we can explore all possible paths.

Here is the detailed algorithm:

1. Initialize an empty result list to store all the paths.
2. If the root node is None, return an empty list.
3. Define a helper function called dfs which takes four parameters:
   • The current node n.
   • The current path p (a list of integers representing nodes from the root to the current node).
   • The result list res.
4. In the dfs function:
   • If n is a leaf node:
     • Append the current path p to the result list res.
   • If n has a left child:
     • Recursively call dfs with n.left as the new node, p + [n.left.val] as the new path, and res as the current result list.
   • If n has a right child:
     • Recursively call dfs with n.right as the new node, p + [n.right.val] as the new path, and res as the current result list.
5. Call the dfs function with the root node and an initial path containing only the root node's value.
6. Return the result list.

Here is the Python implementation:

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        def dfs(n, p, res):
            if n.left is None and n.right is None:
                res.append('->'.join(map(str, p)))
            
            if n.left:
                dfs(n.left, p + [n.left.val], res)
            
            if n.right:
                dfs(n.right, p + [n.right.val], res)
            
        if root is None:
            return []

        res = []
        dfs(root, [root.val], res)
        return res

Time Complexity: We visit each node exactly once, so the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity: We use a list to keep track of the current path, and we append each path to the result list. Therefore, the space complexity is O(n) for the worst case if every node is a leaf node.

1