3
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Welcome to Stack Review, please provide an explanation about what the code does and tests. \$\endgroup\$ Feb 5, 2022 at 17:39
  • \$\begingroup\$ the code first converts the tree into an arraylist, so I can then easier print it out. \$\endgroup\$ Feb 5, 2022 at 21:05
  • \$\begingroup\$ I understand, my suggestion was about integrating an explanation and tests into your question to increase the odds of more answers. \$\endgroup\$ Feb 5, 2022 at 21:51
  • 2
    \$\begingroup\$ Can I suggest asking for one review of the whole class, rather than breaking out individual methods into their own questions? You'll get better, more meaningful answers. \$\endgroup\$
    – Eric Stein
    Feb 6, 2022 at 4:41
  • \$\begingroup\$ No need to convert the tree into an arraylist, as you can see in my answer. \$\endgroup\$
    – convert
    Feb 6, 2022 at 14:08

3 Answers 3

3
\$\begingroup\$

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();
}
\$\endgroup\$
1
  • \$\begingroup\$ So why not then directly use StringBuilder instead of ArrayList? \$\endgroup\$
    – convert
    Feb 7, 2022 at 10:30
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ With a Stream you can just use a joining collector. \$\endgroup\$
    – RoToRa
    Feb 7, 2022 at 14:28
  • \$\begingroup\$ @RoToRa thanks for the link. I felt Stream already hard to digest for a beginner, in a review. But you provide again an other feature of the expressiveness of Streams. Worth learning. \$\endgroup\$
    – Joop Eggen
    Feb 7, 2022 at 14:56
1
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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