BinarySearchTree toString method

Question

I have my ToString method right here for my BinarySearchTree class

    private ArrayList<T> inorderList(ArrayList<T> values) {
        if (left != null) {
            left.inorderList(values);
        }
        values.add(data);
        if (right != null) {
            right.inorderList(values);
        }
        return values;
    }

    public String toString() {
        String returnS = "";
        ArrayList<T> values = new ArrayList<T>();
        values = inorderList(values);
        for (int i = 0; i < values.size(); i++) {
            if (i != values.size()-1) {
                returnS += values.get(i) + ", ";
            }
            else {
                returnS += values.get(i);
            }
        }
        return returnS;
    }

This code works, but I'm pretty sure it's inefficient/ugly, and I'm wondering if it looks alright, or if there's any way I can clean up my code.

Answer 1

Using an iterator on dynamic structures can simplify your logic and are generally good practice. The classic for-each loop: for (int i : a) uses an iterator under the hood. It also makes your conditional logic a bit more intuitive (while the iterator has a next token, place a comma) rather than relying on indexing. This doesn't add any performance benefit, but is something to keep in mind.

Every time you loop, you concatenate to a string. This is inefficient as String is immutable, and you therefore create a copy of it every time you make a change to it. StringBuilder was optimized for this, as a singular character is appended each time-- this results in a more optimal performance when building a string like you are doing

public String toString() {
    ArrayList<T> values = new ArrayList<T>();
    values = inorderList(values);
    final Iterator<T> valuesIterator = values.iterator();
    StringBuilder out = new StringBuilder();
    while (valuesIterator.hasNext()) {
        out.append(valuesIterator.next());
        if (valuesIterator.hasNext()) {
            out.append(",");
        }
    }
    return out.toString();
}

Answer 2

First, one sees you are still a beginner, hence first some pointer to improving code. And after that your question to general improvement, where you were correct to suspect there should be something better.

• inorderList returns its parameter, so can simply return void.
• It is better to program against interfaces, as then the implementation is free, you can later change the implementation class. You can assign Collections.emptyList(), Collections.singletonList(), Collections.asList.
• You can use the diamond operator <> saving repetitive typing.
• StringBuilder is a utility class to prevent inefficient String concatenation with +/+= (100 +=s would create 100 new strings, dropping 99 old strings).
• Always use @Override as that detects typos public String toSting().
• I show below the usage of a more compact for-each loop.

So:

private void inorderList(List<T> values) {
    if (left != null) {
        left.inorderList(values);
    }
    values.add(data);
    if (right != null) {
        right.inorderList(values);
    }
}

@Override
public String toString() {
    List<T> values = new ArrayList<>();
    inorderList(values);
    StringBuilder sb = new StringBuilder();
    for (T value: values) {
        if (sb.length() != 0) {
            sb.append(", ");
        }
        sb.values.append(value);
    }
    return sb.toString();
}

A a comma separated string from multiple items, there exists a utility functions.

But let just answer your original question. Instead of collecting first a possibly huge ordered list, you can visit every node with a piece of code. There are several forms, but the latest is the Stream<T>.

A usage example would be:

    values.stream().forEach(v -> { // T v
        if (sb.length() != 0) {
            sb.append(", ");
        }
        sb.values.append(v);
    });

But Stream is a very expressive and unavoidable class.

The implementation of the stream is more sophisticated.

public Stream<T> stream() {
    Stream s = Stream.of(data);
    if (left != null) {
        s = Stream.concat(left.stream(), s);
    }
    if (right != null) {
        s = Stream.concat(s, right.stream());
    }
    return s;
}

Realize that Stream does not start to iterate until a "final" operation is done such as forEach, collect, count, sum.

Now you could do:

@Override
public String toString() {
    stream().forEach(v -> {
        if (sb.length() != 0) {
            sb.append(", ");
        }
        sb.values.append(v);
    });
    return sb.toString();
}

With variations, like skipping empty strings.

    stream()
        .filter(Objects::notNull)  // T v. Means: v -> Objects.notNull(v).
        .map(v -> v.toString())    // T v. Or: Object::toString.
        .filter(v -> !v.isBlank()) // String v.
        .forEach(v -> {
            if (sb.length() != 0) {
                sb.append(", ");
            }
            sb.values.append(v);
        });
    return sb.toString();
}

This is a bit much, and it is not necessary to start programming high javanese.

Answer 3

It makes no sence to put all elements of a tree to a list just to put them later to string in some defined order. This task can be completed directly. So here improoved version of toString:

public String toString( {
      String str="";
      if (left != null) str+=left+ ", ";
      str+=data;
      if (right != null) str+=", "+right;
      return str;
    }

I personaly have never heared about StringBuilder befor, so haven´t used it myself. After taking a look at the docs, solution using StringBuilder could look like this:

private void inorderString(StringBuilder strings) {
        if (left != null) {
            left.inorderString(strings);
            strings.add(", ");
        }
        strings.add(data);
        if (right != null) {
            strings.add(", ");
            right.inorderList(strings);
        }
    }

    public String toString() {
        StringBuilder strings = new StringBuilder();
        inorderString(strings);
        return strings.toString();
    }