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