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.

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