Finding all root-to-leaf paths in a binary tree

Question

The task is to return all root-to-leaf paths, given a binary tree (from leetcode).

This is my approach.

1. Take a helper array and a counter, keeping track of what has been traversed so far. If it is leaf node, print all till that point.
2. Reduce counter.

Please suggest improvements, if any.

import java.util.LinkedList;
import java.util.List;
public class LeafNode {
 private List<String> list;
 private int count = -1;//counts no. of element in print array
 private int[] printArray;// a helper array class to print nodes
 public List<String> binaryTreePaths(TreeNode root) {
 list = new LinkedList<>();
 if(root == null){
 return list;
 }
 printArray = new int[10000];// assuming the maximum size will be less than 10000
 printList(root);
 return list;
 }
 private void printList(TreeNode root) {
 printArray[++count] = root.val;
 if(root.left == null && root.right == null) {
 printTillNow();
 } else{
 if(root.left != null) {
 printList(root.left);
 }
 if(root.right != null){
 printList(root.right);
 }
 }
 --count;
 }
//just prints all the nodes so far
 private void printTillNow() {
 if(count < 0){
 return;
 }
 StringBuilder sb = new StringBuilder();
 int i =0;
 for(i = 0; i<count; i++){
 sb.append(printArray[i]);
 sb.append("->");
 }
 sb.append(printArray[i]);
 list.add(sb.toString());
 }
}

Answer 1

Names

What is the purpose of this class? My first thought when I see a class named LeafNode is that it's a model of a leaf node in a tree. But this class is not about modeling trees. The purpose of this class seems to be to contain the method binaryTreePaths, which returns a list of paths to all leaf nodes of the Tree parameter it receives.

A better (but still not great) name for this class would have been the name of the exercise: BinaryTreePaths.

The term "print" comes up several times, but there's nothing in the exercise about printing. The task is to return a list of strings. No printing. The overuse of this term throughout the implementation is misleading, confusing, noise.

Choice of storage

If you don't know the required size of a collection in advance, prefer a List, which can dynamically resize itself, such as an ArrayList, instead of a fixed size array. ArrayList exists exactly for this purpose.

Fragile state tracking

This class has a state, represented by the fields list, count, printArray. It's difficult to follow the state changes, as all methods may (and do) change these variables.

I recommend using so-called accumulator parameters. You pass an accumulator variable to recursive method calls, which append values appropriately. Consider this alternative implementation, using paths as an accumulator variable:

public List<String> binaryTreePaths(TreeNode root) {
 if (root == null) {
 return Collections.emptyList();
 }
 List<String> paths = new ArrayList<>();
 binaryTreePaths(root, "" + root.val, paths);
 return paths;
}
public void binaryTreePaths(TreeNode root, String prefix, List<String> paths) {
 if (root.left == null && root.right == null) {
 paths.add(prefix);
 return;
 }
 if (root.left != null) {
 binaryTreePaths(root.left, prefix + "->" + root.left.val, paths);
 }
 if (root.right != null) {
 binaryTreePaths(root.right, prefix + "->" + root.right.val, paths);
 }
}

This improves in the original in simplicity.

Alternative implementation

Another variation on the previous solution, but using a StringBuilder instead of string concatenation:

public List<String> binaryTreePaths(TreeNode root) {
 if (root == null) {
 return Collections.emptyList();
 }
 List<String> paths = new ArrayList<>();
 binaryTreePaths(root, new StringBuilder("" + root.val), paths);
 return paths;
}
public void binaryTreePaths(TreeNode root, StringBuilder builder, List<String> paths) {
 if (root.left == null && root.right == null) {
 paths.add(builder.toString());
 return;
 }
 if (root.left != null) {
 int len = builder.length();
 binaryTreePaths(root.left, builder.append("->").append(root.left.val), paths);
 builder.setLength(len);
 }
 if (root.right != null) {
 binaryTreePaths(root.right, builder.append("->").append(root.right.val), paths);
 }
}

Answer 2

Names

list is a bad name for variable. What does it store?

printTillNow - does this function print anything? It rather prepares the data to be printed.

count - maybe numElementsInPrintArray?

Magic number

Instead of printArray = new int[10000];// assuming the maximum size will be less than 10000, you can write printArray = new int[MAXIMUM_ARRAY_SIZE];