Why it is Suboptimal

While BFS finds the shortest path in unweighted graphs, "Binary Tree Paths" requires all paths. BFS does not offer an algorithmic advantage here and often requires more complex code to manage the queue of pairs (Node, String). The recursive structure of trees naturally lends itself to a DFS solution, which is generally cleaner to implement and easier to reason about for full-tree traversals.

Core Insight for Binary Tree Paths

The key intuition for the LeetCode 257 solution is that a path from the root to any node N is simply the path from the root to N's parent, extended by N.

By using Recursive Preorder Traversal, we can pass the "history" of the path down the recursion stack. When the recursive function is called for a specific node, it receives the partial path constructed so far.

Algorithm Invariants

1. State Passing: The recursive function carries the current_path string as an argument.
2. Leaf Detection: The decision to "commit" a path to the final answer happens strictly when a leaf node is identified (both children are null).
3. Immutable State (Conceptual): By passing the path string by value (or creating a new string for the next call), we ensure that the left subtree's path construction does not interfere with the right subtree's path construction. Each branch gets its own copy of the path.

Visual Description

Imagine the recursion tree. Execution starts at the root. The algorithm appends "1". It then pauses the root's context and moves left to "2", passing "1->2". It reaches a leaf, saves "1->2", and returns. The recursion unwinds back to "1", which then calls the right child "3", passing "1->3". The branching of the tree structure mirrors the branching of the string construction.

Algorithm Strategy: Tree DFS - Recursive Preorder Traversal

We will implement a dfs helper function that takes the current node and the current_path string.

1. Base Case (Null Check): If the current node is null, return immediately. This handles edge cases and simplifies leaf logic.
2. Update Path: Append the current node's value to the current_path. If the current_path was not empty, precede the value with "->".
3. Leaf Check: Check if the current node is a leaf (i.e., node.left == null and node.right == null).
   • If yes, add the current_path to our global result list.
4. Recursive Step:
   • Call dfs on node.left with the updated current_path.
   • Call dfs on node.right with the updated current_path.

This strategy ensures we visit every node exactly once and construct paths in a top-down manner.

Execution Flow

Let's trace the algorithm with Input: root = [1, 2, 3, null, 5]

1. Call DFS(1, ""):

   • Path becomes "1".
   • Node 1 is not a leaf.
   • Recurse Left: DFS(2, "1").

2. Inside DFS(2, "1"):

   • Path becomes "1->2".
   • Node 2 is not a leaf (has right child 5).
   • Recurse Left: DFS(null, "1->2") -> Returns immediately.
   • Recurse Right: DFS(5, "1->2").

3. Inside DFS(5, "1->2"):

   • Path becomes "1->2->5".
   • Node 5 is a leaf (left and right are null).
   • Action: Add "1->2->5" to result list.
   • Returns to Node 2 context.

4. Back in DFS(2, "1"):

   • Both children processed. Returns to Node 1 context.

5. Back in DFS(1, ""):

   • Recurse Right: DFS(3, "1").

6. Inside DFS(3, "1"):

   • Path becomes "1->3".
   • Node 3 is a leaf.
   • Action: Add "1->3" to result list.
   • Returns to Node 1 context.

7. Final Result: ["1->2->5", "1->3"].

Proof of Correctness

The correctness relies on the structural induction of the binary tree:

1. Basis: For a single-node tree (root only), the algorithm appends the root value, detects it as a leaf, and returns the single correct path.
2. Inductive Step: Assume the algorithm correctly constructs paths for any subtree rooted at L (left) and R (right). When at the parent P, the algorithm constructs the prefix "Path(Root...P)". It then passes this prefix to L. By assumption, L will complete all paths starting with "Path(Root...P)->L...". The same applies to R.
3. Completeness: Since DFS visits every node, and the leaf check ensures we only store completed paths, the result contains all valid root-to-leaf paths.

Reference Implementation

C++ Solution for LeetCode 257

cpp
class Solution {
public:
    void dfs(TreeNode* node, string path, vector<string>& result) {
        if (!node) return;
        
        // Append current node value
        path += to_string(node->val);
        
        // Check if it is a leaf node
        if (!node->left && !node->right) {
            result.push_back(path);
        } else {
            // If not a leaf, continue traversal with arrow
            path += "->";
            dfs(node->left, path, result);
            dfs(node->right, path, result);
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        dfs(root, "", result);
        return result;
    }
};

Java Solution for LeetCode 257

java
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root != null) {
            dfs(root, "", result);
        }
        return result;
    }

    private void dfs(TreeNode node, String path, List<String> result) {
        // Append current node to path
        path += Integer.toString(node.val);
        
        // Check if leaf
        if (node.left == null && node.right == null) {
            result.add(path);
        } else {
            // Recurse with arrow appended
            path += "->";
            if (node.left != null) dfs(node.left, path, result);
            if (node.right != null) dfs(node.right, path, result);
        }
    }
}

Python Solution for LeetCode 257

python
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        result = []
        
        def dfs(node, path):
            if not node:
                return
            
            # Construct current path
            path += str(node.val)
            
            # If leaf, add to result
            if not node.left and not node.right:
                result.append(path)
            else:
                # Recurse
                dfs(node.left, path + "->")
                dfs(node.right, path + "->")
        
        dfs(root, "")
        return result