Problem Explanation

This problem requires us to traverse a binary tree and list out all possible paths from the root node down to the leaf nodes. A binary tree is a type of tree data structure where each node can have a maximum of two child nodes. The leaf nodes, meanwhile, are defined as nodes that have no child nodes; these nodes will mark the end of a path.

The challenge here lies in efficiently traversing the tree, and correctly forming and recording all possible paths from the root to the leaves.

For example, consider the following binary tree

1
2
3   1
4 /   \
52     3
6 \
7  5

The binary tree here has two paths from root to leaf:

• 1->2->5 (root to leaf through the left child nodes)
• 1->3 (root to right leaf node)

Solution Approach

To solve this problem, we will use Depth-First Search (DFS). DFS is an algorithm for traversing a tree (or graph) data structure starting at the root (or an arbitrary node) and explores as far as possible along each branch before backtracking.

We start at the root and traverse down to the leaves along each branch depth-first, while maintaining a record of the path taken from root to the current node. We continuously add the current node value to the current path. Once we reach a leaf node (a node with no children), we add the current path to the final list of paths.

For the given binary tree:

1
2
3   1
4 /   \
52     3
6 \
7  5

The DFS traversal would be as follows

1. Starting at root node (1), the current path is "1->"
2. Move to the left child node (2), and append to the path, current path is now "1->2->"
3. Move to the right child node of 2 which is (5), and append to the path, current path is now "1->2->5". Since 5 is a leaf node, we add "1->2->5" to our output paths list
4. We backtrack to node 2 and since it does not have a left child, we do nothing
5. We finish with the left subtree, and we move onto the right subtree (3), and append to the path, current path is "1->3". Since 3 is also a leaf node, we add "1->3" to our output paths list

Hence, our final output paths are ["1->2->5", "1->3"]

Now, after understanding the approach, let's see the code solution in various languages.

Python Solution

1
2python
3class Solution:
4    def binaryTreePaths(self, root):
5        if not root:
6            return []
7        res = []
8        self.dfs(root, "", res)
9        return res
10        
11    def dfs(self, root, path, res):
12        if not root.left and not root.right:
13            res.append(path + str(root.val))
14        else:
15            if root.left:
16                self.dfs(root.left, path + str(root.val) + "->", res)
17            if root.right:
18                self.dfs(root.right, path + str(root.val) + "->", res)

Java Solution

1
2java
3class Solution {
4    public List<String> binaryTreePaths(TreeNode root) {
5        List<String> answer = new ArrayList<>();
6        if (root != null) searchBT(root, "", answer);
7        return answer;
8    }
9    private void searchBT(TreeNode root, String path, List<String> answer) {
10        if (root.left == null && root.right == null) answer.add(path + root.val);
11        if (root.left != null) searchBT(root.left, path + root.val + "->", answer);
12        if (root.right != null) searchBT(root.right, path + root.val + "->", answer);
13    }
14}

JavaScript Solution

1
2javascript
3var binaryTreePaths = function(root) {
4    if(!root) return []
5    let result = []
6    dfs(root, [], result)
7    return result
8};
9
10function dfs(root, path, result) {
11    path.push(root.val)
12    if(!root.left && !root.right) {
13        result.push(path.join('->'))
14    }
15    root.left && dfs(root.left, Array.from(path), result)
16    root.right && dfs(root.right, Array.from(path), result)
17}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<string> binaryTreePaths(TreeNode* root) {
6        vector<string> result;
7        if(root)
8            dfs(root, "", result);
9        return result;
10    }
11    
12    void dfs(TreeNode* root, string path, vector<string>& result) {
13        path += to_string(root->val);
14        if(!root->left && !root->right)
15            result.push_back(path);
16        else {
17            path += "->";
18            if(root->left)
19                dfs(root->left, path, result);
20            if(root->right)
21                dfs(root->right, path, result);
22        }
23    }
24};

C# Solution

1
2csharp
3public class Solution {
4    public IList<string> BinaryTreePaths(TreeNode root) {
5        List<string> result = new List<string>();
6        if (root != null) 
7            SearchPaths(root, "", result);
8        return result;
9    }
10
11    private void SearchPaths(TreeNode root, string path, IList<string> result) {
12        if (root.left == null && root.right == null) 
13            result.Add(path + root.val);
14        if (root.left != null) 
15            SearchPaths(root.left, path + root.val + "->", result);
16        if (root.right != null) 
17            SearchPaths(root.right, path + root.val + "->", result);
18    }
19}

All these solutions follow a top-down approach and use recursive DFS. Each recursion call deals with a node (root) and its left and right children. For each node, recursion or no recursion depends on whether the node exists. If it does, we then check if this node is a leaf node (a node with no child nodes). If so, we add it to our path. After this, we conduct recursive calls for its children. All the solutions have a time complexity of O(N), where N is a number of nodes, since we visit each node not more than two times.The space complexity depends on the size of the output paths list. In the worst case scenario, all paths from the root to the leaf are the longest possible. The number of paths depends on the tree shape, and in the worst case, it can be O(N/2) for full binary tree. In sum, the function could keep up to N strings of length N for the paths list, and a string of length N for the recursion stack, hence resulting in a space complexity of O(N^2).

This is a fairly straightforward and efficient approach to solve the problem and works with any binary tree. However, if the binary tree is too large, the recursive approach may lead to a stack overflow. An iterative approach using Breath-First Search or Depth-First Search with an explicit stack could be the alternative to avoid the stack overflow.

In general, dealing with tree-based data structures requires a good understanding of recursive functions and traversal algorithms. This problem is a good example to explain these concepts. Until next time, happy coding!