Find all root to leaf paths in binary tree

Question

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;
 path.add(""+root.val);
 if (root.left == null && root.right == null) {
 paths.add(String.join("->", path));
 }
 traverse(root.left, path, paths);
 traverse(root.right, path, paths);
 path.remove(path.size() - 1);
 }
}

Answer 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) {
 paths.add(sb.substring(2));
}
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.

• CodeYogi: I thought about it too but went with the generic approach. Also, I am finding this pattern very easy to understand.

Answer 2

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));