Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
/ \
2 3
\
5
All root-to-leaf paths are:

[“1->2->5”, “1->3”]

O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new LinkedList<>();
        if (root != null) findPath(root, new StringBuilder(), paths);
        return paths;
    }
    
    private void findPath(TreeNode root, StringBuilder sb, List<String> paths) {
        if (root != null) {
            int length = sb.length();
            sb.append(root.val);
            if (root.left == null && root.right == null) {
                paths.add(sb.toString());
            } else {
                sb.append("->");
                findPath(root.left, sb, paths);
                findPath(root.right, sb, paths);
            }
            sb.setLength(length);
        }
    }
}

A bottom up but unefficient solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<String> binaryTreePaths(TreeNode root) {
        
        List<String> paths = new LinkedList<>();

        if(root == null) return paths;
        
        if(root.left == null && root.right == null){
            paths.add(root.val+"");
            return paths;
        }

         for (String path : binaryTreePaths(root.left)) {
             paths.add(root.val + "->" + path);
         }

         for (String path : binaryTreePaths(root.right)) {
             paths.add(root.val + "->" + path);
         }

         return paths;
        
    }