Solution Explanation:

This problem asks to find all root-to-leaf paths in a binary tree. A root-to-leaf path is a sequence of nodes from the root node to a leaf node (a node with no children). The solution uses Depth-First Search (DFS) with backtracking to efficiently explore all paths.

Approach:

The core idea is to recursively traverse the tree. For each node:

1. Append the node's value: Add the current node's value to a temporary path (represented as a list or string in the code examples).
2. Check for leaf node: If the current node is a leaf node (no left or right child), append the current path to the result list.
3. Recurse: If the current node is not a leaf node, recursively call the DFS function on its left and right children. This explores paths branching from the current node.
4. Backtrack: After processing a node's children, remove the node's value from the temporary path. This "backtracks" to the previous node, enabling exploration of alternative paths.

Code Explanation (Python Example):

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        ans = []  # Result list to store paths
        t = []    # Temporary list to build current path
 
        def dfs(node):
            if node is None:
                return
 
            t.append(str(node.val))  # Append node value (converted to string)
 
            if node.left is None and node.right is None:  # Leaf node reached
                ans.append("->".join(t))  # Add path to result
 
            else:
                dfs(node.left)  # Explore left subtree
                dfs(node.right) # Explore right subtree
 
            t.pop()  # Backtrack: Remove last element before returning
 
        dfs(root)
        return ans
 

The other language examples follow a similar structure:

• They define a recursive helper function (dfs) to perform the Depth-First Search.
• They use a temporary data structure (t) to store the path as it is being built.
• The path is added to the result (ans) only when a leaf node is reached.
• Backtracking is implemented by removing the last element of the temporary structure after processing a node.

Time Complexity:

The time complexity is O(N), where N is the number of nodes in the binary tree. This is because each node is visited and processed exactly once during the DFS traversal.

Space Complexity:

The space complexity can be:

• O(H) in the best case: H is the height of the tree, if we consider the recursion stack space only. This occurs in balanced trees.
• O(N) in the worst case: In a skewed tree, the height can be equal to N (number of nodes), leading to O(N) space complexity. We also need O(N) space in the worst case to store the resulting paths (if all paths are very long).

The overall space complexity is dominated by the recursion stack and the storage of the results, making it O(N) in the worst case.