Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def binaryTreePaths(self, root):
        def construct_paths(node, path, paths):
            if node:
                path += str(node.val)
                # if leaf node, append path to paths
                if not node.left and not node.right:
                    paths.append(path)
                else:
                    path += '->'
                    construct_paths(node.left, path, paths)
                    construct_paths(node.right, path, paths)

        paths = []
        construct_paths(root, '', paths)
        return paths
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void constructPaths(TreeNode* node, string path, vector<string>& paths) {
        if (node) {
            path += to_string(node->val);
            if (!node->left && !node->right) {
                paths.push_back(path);
            } else {
                path += "->";
                constructPaths(node->left, path, paths);
                constructPaths(node->right, path, paths);
            }
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        constructPaths(root, "", paths);
        return paths;
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        constructPaths(root, "", paths);
        return paths;
    }
    
    private void constructPaths(TreeNode node, String path, List<String> paths) {
        if (node != null) {
            path += node.val;
            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                path += "->";
                constructPaths(node.left, path, paths);
                constructPaths(node.right, path, paths);
            }
        }
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    const paths = [];
    function constructPaths(node, path) {
        if (node) {
            path += node.val;
            if (!node.left && !node.right) {
                paths.push(path);
            } else {
                path += '->';
                constructPaths(node.left, path);
                constructPaths(node.right, path);
            }
        }
    }
    constructPaths(root, '');
    return paths;
};
      

Problem Description

Given the root of a binary tree, return all root-to-leaf paths in any order. Each path should be represented as a string with node values separated by "->". A leaf is a node with no children.

• There may be multiple valid paths, and you should return all of them.
• You must not reuse nodes; each path must start from the root and end at a leaf, traversing each node only once in a path.
• Each node value should appear in the path exactly as it appears in the tree.

For example, for the tree:

        1
       / \
      2   3
       \
        5
    

Thought Process

To solve this problem, we need to find all paths from the root of the tree to its leaves. At first, we might think of traversing all possible paths in the tree and collecting those that end at a leaf. This suggests a recursive approach, as we can process each node and recursively build up the path as we move down the tree.

The brute-force idea would be to try every possible path, but since the tree is acyclic and each node is used only once per path, this is just a traversal. The main challenge is to keep track of the path as we go, and to output it in the required string format.

We also need to decide when a path is complete (i.e., when we hit a leaf node), and then add the current path to our result list. The recursive call should build up the path step by step, appending the current node's value.

Solution Approach

We use a depth-first search (DFS) traversal to explore all root-to-leaf paths.

• Recursive Traversal: We start at the root and recursively traverse down the left and right children.
• Path Construction: As we move from the root to a node, we build a string representing the path so far. At each step, we append the current node's value to the path. If the current node is not a leaf, we also append "->" to the path.
• Leaf Node Detection: When we reach a node that has no left or right child (i.e., a leaf), we add the constructed path string to our result list.
• Result Collection: We collect all such paths in a list and return it at the end.

This approach is efficient because each node is visited exactly once, and the path string is constructed as we go, so no extra traversal or backtracking is needed.

1. Initialize an empty result list for paths.
2. Define a helper function that takes the current node, the path so far, and the result list.
3. At each call, add the current node's value to the path string.
4. If the node is a leaf, add the path string to the result list.
5. If not, recursively call the helper for the left child and right child (if they exist), appending "->" as needed.
6. Return the result list after traversal.

Example Walkthrough

Let's use the sample tree:

        1
       / \
      2   3
       \
        5
    

• Start at root (1), path = "1"
• Go left to (2), path = "1->2"
• (2) has right child (5): go right to (5), path = "1->2->5"
• (5) is a leaf: add "1->2->5" to result
• Back at (1), go right to (3), path = "1->3"
• (3) is a leaf: add "1->3" to result

Final output: ["1->2->5", "1->3"]

Time and Space Complexity

• Brute-force: In a brute-force approach, if we tried to enumerate all possible sequences through the tree, the complexity could be exponential, but since the tree is acyclic and we only move from root to leaves, we visit each node once.
• Optimized Approach: The DFS solution visits each node exactly once, so the time complexity is O(N), where N is the number of nodes in the tree.
• Space Complexity: The space complexity is also O(N) for the recursion stack (in the worst case, for a skewed tree) and for storing the output paths (since each path could be up to O(N) in length).

Summary

The binary tree paths problem is elegantly solved using a recursive depth-first search. By building up the path string as we traverse from the root to each leaf, we efficiently collect all valid root-to-leaf paths. The solution is simple, clear, and leverages recursion to naturally explore all possible paths, with time and space complexity linear in the number of nodes.