Simple toString() method for Binary Search Trees

If you are unfamiliar with tree-traversal techniques such as inorder, postorder, and preorder, I would recommend reading this article first.

Given a binary tree such as this:

A binary tree, which happens to also be a binary search tree.

If you want to print out the string:

1234567

Then you can call a println() as your “visit” operation, as mentioned in the tree-traversal article.

But what if you wanted to return the String?

Strategy

Build on previous knowledge

• We know that we have to traverse the entire tree in order to print out all of the elements
• We know three different tree traversals: preorder, inorder, postorder
• We can concatenate strings using the ‘+’ operator

Algorithm steps

1. Initialize an empty String s to represent out string output
2. If the root is null, we return null
3. Append to s the result of the root.toString()
4. Recursively call the toString(TreeNode) method, on the children of the root, and append the result to s
5. Return s

Code

Preorder

public String toStringPreorder(TreeNode<E> root) {
    String s = "";
    if (root == null) {
        return "";
    }

    s += root.toString();
    s += toStringPreorder(root.left);
    s += toStringPreorder(root.right);
    return s;
}

Result on example tree above: dbacfeg

Postorder

public String toStringPostOrder(TreeNode<E> root) {
    String result = "";
    if (root == null) {
        return "";
    }

    result += toStringPostOrder(root.left);
    result += toStringPostOrder(root.right);
    result += root.toString();
    return result;
}

Result on example tree above: acbegfd

Inorder

public String toStringInorder(TreeNode<E> root) {
    String s = "";
    if (root == null) {
        return "";
    }

    s += toStringInorder(root.left);
    s += root.toString();
    s += toStringInorder(root.right);
    return s;
}

Result on example tree above: abcdefg

Conclusion

This is a simple way to output the contents of your trees. Thanks for reading!