Naive Solution: Depth-First Search (DFS) - Brute Force

The most straightforward approach is to use Depth-First Search (DFS) to traverse the binary tree. We explore each possible path from the root to a leaf node. As we traverse, we build the path string. When we reach a leaf node, we add the path to our result.

Algorithm:

1. Initialize an empty list to store the paths.
2. Define a recursive function dfs(node, current_path):
   • If the 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 and right children):
     • Add the current_path to the list of paths.
     • Return.
   • If the current node is not a leaf node:
     • Recursively call dfs on the left child, updating current_path.
     • Recursively call dfs on the right child, updating current_path.
3. Call the dfs function starting from the root with an empty current_path.
4. Return the list of paths.

Code:

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


def binaryTreePaths(root):
    if not root:
        return []

    paths = []

    def dfs(node, path):
        if not node.left and not node.right:
            paths.append(path + str(node.val))
            return
        
        if node.left:
            dfs(node.left, path + str(node.val) + "->")
        if node.right:
            dfs(node.right, path + str(node.val) + "->")

    dfs(root, "")
    return paths

Time Complexity:

• O(N), where N is the number of nodes in the tree. We visit each node once.

Space Complexity:

• O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H can be N, resulting in O(N) space.

Optimal Solution: Depth-First Search (DFS) - Optimized String Building

While the previous solution is conceptually simple, the repeated string concatenation in each recursive call can introduce overhead. An optimized approach involves using a list to store the path and only converting it to a string when a leaf node is reached.

Algorithm:

1. Initialize an empty list to store the paths.
2. Define a recursive function dfs(node, current_path):
   • If the 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 and right children):
     • Convert the current_path list to a string using "->" as a separator and add it to the list of paths.
     • Return.
   • If the current node is not a leaf node:
     • Recursively call dfs on the left child, updating current_path.
     • Recursively call dfs on the right child, updating current_path.
   • Before returning from a non-leaf node, remove the last element of the current_path to backtrack correctly.
3. Call the dfs function starting from the root with an empty current_path.
4. Return the list of paths.

Code:

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


def binaryTreePaths(root):
    if not root:
        return []

    paths = []

    def dfs(node, path):
        if not node:
            return
        
        path.append(str(node.val))

        if not node.left and not node.right:
            paths.append("->".join(path))
        else:
            if node.left:
                dfs(node.left, path)
            if node.right:
                dfs(node.right, path)
        path.pop()

    dfs(root, [])
    return paths

Time Complexity:

• O(N), where N is the number of nodes in the tree. We still visit each node once.

Space Complexity:

• O(H), where H is the height of the tree, due to the recursion stack and the current_path list. In the worst case (skewed tree), H can be N, resulting in O(N) space.

Edge Cases:

• Empty Tree: If the root is None, return an empty list.
• Single Node Tree: If the root is the only node (a leaf), return a list containing the root's value as a string.
• Skewed Tree (Left or Right): The algorithm should handle skewed trees correctly, traversing all nodes to the leaf.