Printing a Binary Tree

[Aj Prieto]

I'm trying to write a method that prints out the contents of a binary tree.

It's supposed to print the contents out this way.

//If the tree looked like this
     15
    /  \
   12  18
  /   /  \
 10  16  20
   \   \
   11  17

//It's supposed to print it out this way.
|15
|<12
|<<10
|<<>11
|>18
|><16
|><>17
|>>20

My code:

public class BinarySearchTree<E extends Comparable<E>> {

  private TreeNode<E> root = null;
  private int size = 0;
  private String printTree = "";

  /** Creates an empty tree. */
  public BinarySearchTree() {
  }
  
  /** Creates a List from the Collection, shuffles it, then builds a new tree with the elements. */
  public BinarySearchTree(Collection<E> col){
	List<E> list = new ArrayList<E>(col);
	Collections.shuffle(list);
		
		//Builds new BST
		for (int x = 0; x < list.size(); x++){
			add(list.get(x));
		}		
  }
  
  public String toFullString(){
  	toFullString(root);
	return printTree;
 }
 
 private String toFullString(TreeNode<E> root){
  	if (root == null){
		return "";
	}
	
	printTree += root.getData()+" | ";
	printTree += toFullString(root.getLeft());
	printTree += toFullString(root.getRight());
	

	return printTree;
}

My output
18 | 18 | 12 | 18 | 12 | 11 | 18 | 12 | 11 | 10 | 18 | 12 | 18 | 12 | 11 | 18 | 12 | 11 | 10 | 17 | 18 | 12 | 18 | 12 | 11 | 18 | 12 | 11 | 10 | 17 | 16 | 18 | 12 | 18 | 12 | 11 | 18 | 12 | 11 | 10 | 17 | 16 | 15 | 18 | 18 | 12 | 18 | 12 | 11 | 18 | 12 | 11 | 10 | 18 | 12 | 18 | 12 | 11 | 18 | 12 | 11 | 10 | 17 | 18 | 12 | 18 | 12 | 11 | 18 | 12 | 11 | 10 | 17 | 16 | 18 | 12 | 18 | 12 | 11 | 18 | 12 | 11 | 10 | 17 | 16 | 15 | 20 |

What I need help on, is why does it print it out that way? Is my method wrong (most likely it is) or am I missing something small. It's supposed to print in preorder traversal order.

Thanks in advance.

[Campbell Ritchie]

I have had to remove some of your code tags because the long line is very difficult to read in side code tags.

Please explain the rules you want to apply to printing. If a value is on the left, then you prepend it with a < and if it is the right branch a >? And the number of arrowheads depends on the depth you find that value at? And your nine‑element tree prints such a long
I would suggest you get a pencil and paper, going through that tree and working out how you are going to get a String together. It looks to me like a prime candidate for recursion. So start by working out how you are going to print a base case, for example a tree which looks like this:-

 |
123

Remember that tree will be represented by a node with its left and right references both pointing to null. Once you have got that working, see how you would print trees like

 |
123
   \
    234

or

     |
    123
   /   \
234    345

I would suggest you don’t use the + operator on Strings, because of performance problems. You might not notice anything in that little tree, but it won’t scale to large trees. Use a StringBuilder instead and use its append and insert methods. Note most of the StringBuilder methods do not return void, so you can daisy‑chain calls

String s = "a right nuisance";
System.out.println(
      new StringBuilder("Ritchie").insert(0, ' ').append(" is")
      .append(' ').append(s).insert(0, "Campbell").append('.'));

Warning: do not try passing a char to a StringBuilder constructor.
Note: You can pass a CharSequence to many methods of a StringBulider’s; since StringBulider itself implements CharSequence, that means you can easily append (for example) one StringBuilder to another.
Note 2: You can append or insert characters like | or a line end sequence. The best way to get the line end sequence is probably like this:-
private final String LINE_END = System.getProperty("line.separator");
Check that line carefully in case I have got a misspelling in it.

[Winston Gutkowski]

Aj Prieto wrote:What I need help on, is why does it print it out that way? Is my method wrong...[?]

Well, fairly obviously, it is.

And that's not just a flip comment. If a program is not doing what you want, it's almost always because your code is wrong; so don't start looking to blame anything outside until you can prove that it works; which in your case, you plainly can't.

However, just off the top of my head, I'd say that the heart of your problem lies in trying to do it all in one String. The required output is divided into lines, so I would look to creating an array (or List, or maybe even a Map) of Strings, where each one is a line, and then try to join them all.

I suspect there are several possible solutions though.

But whatever you do, DON'T try to 'code your way out of a jam'.

HIH

Winston

[Campbell Ritchie]

By the way, I think you have the wrong generics. I think it should be <E extends Comparable<? super E>>
That allows a superclass of E to implement the Comparable interface.

[Aj Prieto]

@Campbell Ritchie : Yes, when you print a value on the left you add a "<" and on the right a ">". Also, I don't think your a nuissance.

I know you guys have said that I shouldn't use one string or use the + operator, but I was using them based off of the notes in class, and I would like to try and follow what was given.

Thanks for help, I've figured it out.

[Campbell Ritchie]

Well done Show us what you’ve got.