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