Leetcode 257. Binary Tree Paths

Problem

Given the root of a binary tree, return all paths from the root node to every leaf node in the tree. Each path should be represented as a string with node values separated by "->".

A leaf node is defined as a node with no children (both left and right pointers are null).

Requirements

1. Return an array of strings, where each string represents one complete path from root to leaf
2. Format each path as node values joined with "->" (e.g., "1->2->5")
3. The order of paths in the result array does not matter
4. Handle edge cases like empty trees and single-node trees

Constraints

• The number of nodes in the tree is in the range [0, 100]
• -100 ≤= Node.val ≤= 100
• Each node value can be any integer (including negative numbers)

Examples

Example 1:

` Input: 1 /
2 3 /
5 6

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

Explanation: There are three leaf nodes (5, 6, and 3). The paths from root to each leaf are:

• 1 to 2 to 5: "1->2->5"
• 1 to 2 to 6: "1->2->6"
• 1 to 3: "1->3" `

Example 2:

` Input: 1

Output: ["1"]

Explanation: The tree has only one node, which is both the root and a leaf. `

Example 3:

` Input: 1 / 2 / 3

Output: ["1->2->3"]

Explanation: Only one path exists in this left-skewed tree. `

Hint 2: Identifying Leaves A leaf node is one where both left and right children are null. This is your base case for when to save a complete path.

Hint 3: Building the Path String As you recursively traverse the tree, maintain the current path as a string or list. When moving to a child node, append "->value" to the current path. When backtracking, the function call naturally "undoes" the addition.

Full Solution `` Explanation:

The solution uses a depth-first search (DFS) approach with backtracking:

1. Base Case: If the tree is empty, return an empty list.
2. DFS Helper Function: We define a recursive helper that takes the current node and the path built so far as a string.
3. Path Building: For each node, we append its value to the current path string (with "->" separator if not the first node).
4. Leaf Detection: When we reach a node with no children, we've found a complete root-to-leaf path, so we add it to our results.
5. Recursive Exploration: If the node has children, we recursively explore them, passing the updated path string.
6. Implicit Backtracking: Because we pass the path string by value (strings are immutable in Python), each recursive call works with its own copy, providing automatic backtracking without explicit cleanup.

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree, due to the recursion call stack. In the worst case (skewed tree), this could be O(n).

Alternative Approach: You could also use an iterative approach with a stack, storing tuples of (node, path_string) and processing them in a DFS manner. The logic would be similar but avoids recursion.

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

def binaryTreePaths(root):
    """
    Find all root-to-leaf paths in a binary tree.
    
    Time Complexity: O(n) where n is the number of nodes
    Space Complexity: O(h) for recursion stack where h is height
    """
    if not root:
        return []
    
    result = []
    
    def dfs(node, current_path):
        """Helper function to perform DFS and build paths."""
        if not node:
            return
        
        # Add current node to the path
        if current_path:
            current_path += "->" + str(node.val)
        else:
            current_path = str(node.val)
        
        # If it's a leaf node, add the complete path to result
        if not node.left and not node.right:
            result.append(current_path)
            return
        
        # Recursively explore left and right subtrees
        if node.left:
            dfs(node.left, current_path)
        if node.right:
            dfs(node.right, current_path)
    
    dfs(root, "")
    return result