Naive Solution: Depth-First Search (DFS) with String Concatenation

A straightforward approach is to perform a Depth-First Search (DFS) traversal of the binary tree. During the traversal, we maintain a string representing the current path from the root to the current node. When we reach a leaf node (a node with no children), we add the current path to our list of paths. The downside of this approach is the string concatenation.

Algorithm:

1. Initialize an empty list paths to store the root-to-leaf paths.
2. Define a recursive function dfs(node, current_path):
   • If the current node is None, return.
   • Append the current node's value to the current_path string.
   • If the current node is a leaf node (no left or right child):
     • Add the current_path to the paths list.
     • Return.
   • Recursively call dfs for the left child, updating current_path.
   • Recursively call dfs for the right child, updating current_path.
3. Call the dfs function starting from the root node with an empty string as the initial path.
4. Return the paths list.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def binaryTreePaths(root):
    paths = []

    def dfs(node, current_path):
        if not node:
            return

        current_path += str(node.val)

        if not node.left and not node.right:
            paths.append(current_path)
            return

        if node.left:
            dfs(node.left, current_path + "->")
        if node.right:
            dfs(node.right, current_path + "->")

    dfs(root, "")
    return paths

Time Complexity: O(N^2)

Where N is the number of nodes in the tree. In the worst case, for a skewed tree, the string concatenation in each recursive call can take O(N) time, and we visit each node once.

Space Complexity: O(N)

In the worst case, for a skewed tree, the recursion depth can be O(N). Additionally, storing the paths list can take O(N) space in the worst case.

Optimal Solution: Depth-First Search (DFS) with List and Backtracking

Instead of using string concatenation, we can use a list to store the current path. This avoids the O(N) time complexity of string concatenation in each recursive call. When we reach a leaf node, we convert the list to a string only once. Also, we need to backtrack by removing the last element in list for the next branch.

Algorithm:

1. Initialize an empty list paths to store the root-to-leaf paths.

2. Define a recursive function dfs(node, current_path):

   • If the current node is None, return.
   • Append the current node's value to the current_path list.
   • If the current node is a leaf node (no left or right child):
     • Convert the current_path list to a string with "->" as the separator.
     • Add the string to the paths list.
     • Remove the last element.
     • Return.
   • Recursively call dfs for the left child, updating current_path.
   • Recursively call dfs for the right child, updating current_path.
   • Remove the last element from the current path to backtrack.

3. Call the dfs function starting from the root node with an empty list as the initial path.

4. Return the paths list.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def binaryTreePaths(root):
    paths = []

    def dfs(node, current_path):
        if not node:
            return

        current_path.append(str(node.val))

        if not node.left and not node.right:
            paths.append("->".join(current_path))
            current_path.pop()
            return

        if node.left:
            dfs(node.left, current_path)
        if node.right:
            dfs(node.right, current_path)

        current_path.pop()

    dfs(root, [])
    return paths

Time Complexity: O(N)

Where N is the number of nodes in the tree. We visit each node once, and the list operations (append and pop) take O(1) time. Converting the list to a string takes O(K) where K is the length of the path, but in total this does not exceed O(N).

Space Complexity: O(N)

In the worst case, for a skewed tree, the recursion depth can be O(N). Additionally, storing the paths list can take O(N) space in the worst case. The current_path list also takes O(N) space in the worst case.