1
\$\begingroup\$

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

    }

}
\$\endgroup\$
2
\$\begingroup\$

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);
    }
}
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.