NUHMAN.com

Introduction

LeetCode 257: Binary Tree Paths asks us to find all root-to-leaf paths in a binary tree and return them as strings. It's a common recursive tree traversal problem that helps you understand how to collect and return results from recursive calls.

Problem Statement

Given the root of a binary tree, return all root-to-leaf paths in string format, where each path is represented as:

arduino

"node1->node2->...->nodeN"

Example:

Input:

python

      1
     / \
    2   3
     \
      5

Output:

python

["1->2->5", "1->3"]

Step-by-Step Solution in Python

✅ Step 1: Understand the Goal

• Traverse the tree.
• At each leaf node, record the full path from root to that leaf.
• Use DFS (depth-first search) since we need full paths, and recursion is a natural fit for trees.

✅ Step 2: Choose a Strategy – DFS with Recursion

We’ll use:

• A helper function that builds the path so far
• A result list to collect complete paths
• Recursion to explore both left and right children

Step 3: Code It

python

from typing import Optional, List

class TreeNode:
    def __init__(self, val: int, left: Optional['TreeNode']=None, right: Optional['TreeNode']=None):
        self.val = val
        self.left = left
        self.right = right

def binaryTreePaths(root: Optional[TreeNode]) -> List[str]:
    result = []

    def dfs(node: TreeNode, path: str):
        if not node:
            return
        
        # Add current node to path
        if path:
            path += "->" + str(node.val)
        else:
            path = str(node.val)

        # If it's a leaf node, add the path to the result
        if not node.left and not node.right:
            result.append(path)
            return

        # Recursive DFS
        dfs(node.left, path)
        dfs(node.right, path)

    dfs(root, "")
    return result

Explanation of the Code

• dfs(node, path): Recursively explores the tree, updating the current path.
• Base Case: If the node is a leaf (left and right are None), we add the complete path to result.
• Recursive Case: Continue exploring the left and right children.

Dry Run Example

Input Tree:

text

      1
     / \
    2   3
     \
      5

Paths:

• 1->2->5
• 1->3

Time and Space Complexity

• Time Complexity: O(n), where n = number of nodes (we visit each node once)
• Space Complexity: O(h) for recursion stack (h = height of the tree)

Conclusion

LeetCode 257 is a great introduction to tree traversal with path construction. It shows how to:

• Use DFS to explore all paths
• Build and pass path strings through recursive calls
• Collect results at leaf nodes

You can build on this logic to solve more complex problems like:

• Path sums
• Path counting
• Path matching