# Find all root to leaf paths in binary tree

Description:

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

Leetcode

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/


Code:

class Solution {

public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
traverse(root, new ArrayList<>(), paths);
return paths;
}

private void traverse(TreeNode root, List<String> path, List<String> paths) {
if (root == null) return;

if (root.left == null && root.right == null) {
}

traverse(root.left,  path, paths);
traverse(root.right, path, paths);

path.remove(path.size() - 1);
}
}


It's a fine solution. Tracking the values on the path, growing and shrinking while traversing to the leafs, finally adding a concatenated values is natural and easy to understand.

An alternative (and not necessarily better) approach that may perform better is to reduce the string creation, concatenation by replacing the List<String> for path with a StringBuilder, something like:

int length = sb.length();
sb.append("->").append(root.val);

if (root.left == null && root.right == null) {
}

traverse(root.left,  sb, paths);
traverse(root.right, sb, paths);

sb.setLength(length);


This might be premature optimization, and "clever" code. I think your original is fine as is.

• I thought about it too but went with the generic approach. Also, I am finding this pattern very easy to understand. Jun 26, 2018 at 21:49

regarding the translation from int to String

path.add(""+root.val);


This is both unclear and also involves unnecessary String creation. Why not use the "official" conversion method? it clearly states the intention and is more efficient

path.add(String.valueOf(root.val));