How to effectively print white space as necessary to the task in my prettyPrint() BST method

Question

For the pretty print method of my BST class, we were told by our lecturer for the tree:

    bst.put(7, 7);   //        _7_
    bst.put(8, 8);   //      /     \
    bst.put(3, 3);   //    _3_      8
    bst.put(1, 1);   //  /     \
    bst.put(2, 2);   // 1       6
    bst.put(6, 6);   //  \     /
    bst.put(4, 4);   //   2   4
    bst.put(5, 5);   //        \
                     //         5

The code must print the tree as so:

                    "-7\n" +
                    " |-3\n" + 
                    " | |-1\n" +
                    " | | |-null\n" + 
                    " | |  -2\n" +
                    " | |   |-null\n" +
                    " | |    -null\n" +
                    " |  -6\n" +
                    " |   |-4\n" +
                    " |   | |-null\n" +
                    " |   |  -5\n" +
                    " |   |   |-null\n" +
                    " |   |    -null\n" +
                    " |    -null\n" +
                    "  -8\n" +
                    "   |-null\n" +
                    "    -null\n";

I have got my code to print out the tree almost perfect to what the lecturer as specified using recursion, although I cannot find a way to print the white spaces as he specified. I understand it is a problem with only printing the characters on any right sub tree, but im unsure of a way to correctly print the spaces.

Here is how my code prints:

-7
 |-3
 | |-1
 | | |-null
 | |-2
 | | |-null
 | |-null
 |-6 
 | |-4
 | | |-null
 | |-5
 | | |-null
 | |-null
 |-null
-8
 |-null
-null

As you can see for the right sub tree nodes there is no prefixxed spacing, and any attempt to prefix a space for the right sub tree nodes, has only altered the format of the tree.

Here is my code, any help would be deeply gratified

public String prettyPrintKeys() {
    String output = "";
    int indent = 0;
    output = prettyPrint(root, indent);
    System.out.print(output);
    return output;
}
private String prettyPrint(Node x, int indent){
    String output = "";
    for(int i=0; i<indent; i++){
        output = output + " |";
    }
    if(x == null){
        return output = output + "-null\n";
    }
    indent++;
    output = output + "-" + x.key + "\n" + prettyPrint(x.left, indent);
    indent--;
    output = output + prettyPrint(x.right, indent);
    return output;
}

Answer 1

I normally don't do homework, but this is kinda tricky, and you've done like 90% of the work.

There's a conceptual error you're having. Mainly I think that you can "return" this value somehow. I don't think that works. You have to pass-in your return value so it can be added to, just like you have to pass in the indent variable.

The other problem was that you weren't looking closely at the desired output. There are two indent styles. One for printing a right node, where " |" is printed, and one for a left node, where " " is printed. You have to track those separately.

Here's my attempt, I hope I got it right. ;-)

package quicktest;

/**
 *
 * @author Brenden Towey
 */
public class TreePrint
{

   public static void main( String[] args )
   {
      Node root = new Node();
      fill( root );
      prettyPrintKeys( root );
   }

   public static String prettyPrintKeys( Node root )
   {
//      String output = "";
//      int indent = 0;
      StringBuilder indent = new StringBuilder();
      StringBuilder output = new StringBuilder();

      prettyPrint( root, indent, output );
      System.out.print( output );
      return output.toString();
   }

   private static void prettyPrint( quicktest.TreePrint.Node x,
           StringBuilder indent, StringBuilder output )
   {
//      for( int i = 0; i < indent; i++ )
//         output = output + " |";
      output.append( indent );
//      if( x == null )
//         return output = output + "-null\n";
      output.append( "-" );
      output.append( x );
      output.append( "\n" );
      if( x == null ) return;
//      indent++;
//      output = output + "-" + x.key + "\n" + prettyPrint( x.left, indent );
      indent.append( " |" );
      prettyPrint( x.left, indent, output );
//      indent--;
//      output = output + prettyPrint( x.right, indent );
      indent.delete( indent.length()-2, indent.length() );
      indent.append( "  " );  // <<-- second indent style
      prettyPrint( x.right, indent, output );

      // needed a second indent-- here
      indent.delete( indent.length()-2, indent.length() );
   }

   private static class Node
   {

      Comparable key;
      Node left;
      Node right;

      @Override
      public String toString()
      {
         return "Node{" + "key=" + key + '}';
      }


   }

   private static void fill( Node root )
   {
      insert( root, 7 );
      insert( root, 8 );
      insert( root, 3 );
      insert( root, 1 );
      insert( root, 2 );
      insert( root, 6 );
      insert( root, 4 );
      insert( root, 5 );
   }

   private static void insert( quicktest.TreePrint.Node node, Comparable newKey )
   {
      if( node.key == null ) {
         node.key = newKey;
         return;
      }
      if( node.key.compareTo( newKey ) > 0 ) {
         if( node.left == null ) node.left = new Node();
         insert( node.left, newKey );
         return;
      }
      if( node.right == null ) node.right = new Node();
      insert( node.right, newKey );
   }
}

Output of this program:

run:
-Node{key=7}
 |-Node{key=3}
 | |-Node{key=1}
 | | |-null
 | |  -Node{key=2}
 | |   |-null
 | |    -null
 |  -Node{key=6}
 |   |-Node{key=4}
 |   | |-null
 |   |  -Node{key=5}
 |   |   |-null
 |   |    -null
 |    -null
  -Node{key=8}
   |-null
    -null
BUILD SUCCESSFUL (total time: 0 seconds)