CODEWITHSUNDEEP
javabinary-search-tree
sd2205
sd2205

Reputation: 13

toString method for binary search tree

Please help me to fix my code.

For the toString method, the string should be formatted as 

{currentData, leftSubtree, rightSubtree}

An empty tree should return an empty set of brackets {}.

for the Junit test I'm getting: 

Expected: {5, {0, {-5, {}, {}}, {3, {}, {}}}, {10, {7, {}, {}}, {13, {}, {}}}}
Actual:   {5, {0, {-5, {}, {3, {}, {}, {10, {7, {}, {13, {}, {}, {}}

This is my code:

public String toString() {
    StringBuffer string = new StringBuffer("{");
    toString(root, string);
    string.append("}");
    return string.toString();
}

private void toString(BSTNode<T> node, StringBuffer string) {

    if (node != null) {
        string.append(node.getData());
        if (node.getLeft() != null) {
            string.append(", " + "{");
            toString(node.getLeft(), string);
        }
        if (node.getRight() != null) {
            string.append(", " + "{");
            toString(node.getRight(), string);
        }
    }
    string.append(", {}");
}

Thanks!!

Upvotes: 0

Views: 3784

Answers (1)

Andreas
Andreas

Reputation: 159125

Your code adds { before calling itself recursively, but doesn't add } upon return. This applies to both recursion calls.

Also, your code unconditionally appends , {}, even for non-empty trees.

Instead, write your recursive method to do exactly what you said:

  • Format as {currentData, leftSubtree, rightSubtree}
  • Format empty tree as {}

Don't make it the callers job to add the { } around the value, because that will duplicate the logic (DRY: Don't Repeat Yourself).

Expected output also shows that a leaf node should format as {value, {}, {}}, not as {value}, which is what your code does with those extra if statements.

Also, don't use StringBuffer, use StringBuilder, and the recursive method can be static.

@Override
public String toString() {
    StringBuilder string = new StringBuilder();
    toString(this.root, string);
    return string.toString();
}
private static <T> void toString(BSTNode<T> node, StringBuilder string) {
    string.append('{');
    if (node != null) {
        string.append(node.getData());
        string.append(", ");
        toString(node.getLeft(), string);
        string.append(", ");
        toString(node.getRight(), string);
    }
    string.append('}');
}

If you make the recursive method return the StringBuilder, your code can become smaller, if you like condensing your code. Makes no difference, functionally or performance-wise. It reads better if you flip the parameters.

@Override
public String toString() {
    return toString(new StringBuilder(), this.root).toString();
}
private static <T> StringBuilder toString(StringBuilder string, BSTNode<T> node) {
    string.append('{');
    if (node != null) {
        string.append(node.getData());
        toString(string.append(", "), node.getLeft());
        toString(string.append(", "), node.getRight());
    }
    return string.append('}');
}

Upvotes: 3

Related Questions