title: String Representation of Binary Search Tree
body: <p>I've been trying to write a recursive string method for a binary search tree that returns a multiple line representation of a tree with preorder path info.</p>
  
  <p>Each node should be prefaced by a series of &lt; and > characters showing the path that leads from the root to that node. I'm not sure how to use a string prefix parameter that is extended by one character with each successive call.</p>
  
  <p>The method should be able reproduce this example:</p>
  
  <p>Tree:</p>
  
  <pre><code>     15
      /  \
     12  18
    /   /  \
   10  16  20
     \   \
     11  17
  </code></pre>
  
  <p>Expected Print Output:</p>
  
  <pre><code>15
  &lt;12
  &lt;&lt;10
  &lt;&lt;&gt;11
  &gt;18
  &gt;&lt;16
  &gt;&lt;&gt;17
  &gt;&gt;20
  </code></pre>
  
  <p>I'm new to recursion and so far my actual print output isn't close enough after hours of messing with the code:</p>
  
  <pre><code>18
  &lt;17
  &lt;10
  &gt;15
  &lt;11
  &gt;12
  16
  20
  </code></pre>
  
  <p>Here's my tree node class that works properly:</p>
  
  <pre><code>/**
   * A single binary tree node.
   * &lt;p&gt;
   * Each node has both a left or right child, which can be null.
   */
  public class TreeNode&lt;E&gt; {
  
    private E data;
    private TreeNode&lt;E&gt; left;
    private TreeNode&lt;E&gt; right;
  
    /**
     * Constructs a new node with the given data and references to the
     * given left and right nodes.
     */
    public TreeNode(E data, TreeNode&lt;E&gt; left, TreeNode&lt;E&gt; right) {
      this.data = data;
      this.left = left;
      this.right = right;
    }
  
    /**
     * Constructs a new node containing the given data.
     * Its left and right references will be set to null.
     */
    public TreeNode(E data) {
      this(data, null, null);
    }
  
    /** Returns the item currently stored in this node. */
    public E getData() {
      return data;
    }
  
    /** Overwrites the item stored in this Node with the given data item. */
    public void setData(E data) {
      this.data = data;
    }
  
    /**
     * Returns this Node's left child.
     * If there is no left left, returns null.
     */
    public TreeNode&lt;E&gt; getLeft() {
      return left;
    }
  
    /** Causes this Node to point to the given left child Node. */
    public void setLeft(TreeNode&lt;E&gt; left) {
      this.left = left;
    }
  
    /**
     * Returns this nodes right child.
     * If there is no right child, returns null.
     */
    public TreeNode&lt;E&gt; getRight() {
      return right;
    }
  
    /** Causes this Node to point to the given right child Node. */
    public void setRight(TreeNode&lt;E&gt; right) {
      this.right = right;
    }
  }
  </code></pre>
  
  <p>Here's my binary search tree class with the toFullString() method near the bottom:</p>
  
  <pre><code>import java.util.*;
  
  /**
   * A binary search tree (BST) is a sorted ADT that uses a binary
   * tree to keep all elements in sorted order.  If the tree is
   * balanced, performance is very good: O(n lg n) for most operations.
   * If unbalanced, it performs more like a linked list: O(n).
   */
  public class BinarySearchTree&lt;E extends Comparable&lt;E&gt;&gt; {
  
    private TreeNode&lt;E&gt; root = null;
    private int size = 0;
  
    /** Creates an empty tree. */
    public BinarySearchTree() {
    }
  
  
      public BinarySearchTree(Collection&lt;E&gt; col) {
          List&lt;E&gt; list = new ArrayList&lt;E&gt;(col);
          Collections.shuffle(list);
          for (int i = 0; i &lt; list.size() ; i++) {
              add(list.get(i));
          }
      }
  
  
    /** Adds the given item to this BST. */
    public void add(E item) {
      this.size++;
      if (this.root == null) {
        //tree is empty, so just add item
        this.root = new TreeNode&lt;E&gt;(item);
      }else {
        //find where to insert, with pointer to parent node
        TreeNode&lt;E&gt; parent = null;
        TreeNode&lt;E&gt; curr = this.root;
        boolean wentLeft = true;
        while (curr != null) {  //will execute at least once
          parent = curr;
          if (item.compareTo(curr.getData()) &lt;= 0) {
            curr = curr.getLeft();
            wentLeft = true;
          }else {
            curr = curr.getRight();
            wentLeft = false;
          }
        }
  
        //now add new node on appropriate side of parent
        curr = new TreeNode&lt;E&gt;(item);
        if (wentLeft) {
          parent.setLeft(curr);
        }else {
          parent.setRight(curr);
        }
      }
    }
  
    /** Returns the greatest (earliest right-most node) of the given tree. */
    private E findMax(TreeNode&lt;E&gt; n) {
      if (n == null) {
        return null;
      }else if (n.getRight() == null) {
        //can't go right any more, so this is max value
        return n.getData();
      }else {
        return findMax(n.getRight());
      }
    }
  
    /**
     * Returns item from tree that is equivalent (according to compareTo)
     * to the given item.  If item is not in tree, returns null.
     */
    public E get(E item) {
      return get(item, this.root);
    }
  
    /** Finds it in the subtree rooted at the given node. */
    private E get(E item, TreeNode&lt;E&gt; node) {
      if (node == null) {
        return null;
      }else if (item.compareTo(node.getData()) &lt; 0) {
        return get(item, node.getLeft());
      }else if (item.compareTo(node.getData()) &gt; 0) {
        return get(item, node.getRight());
      }else {
        //found it!
        return node.getData();
      }
    }
  
    /**
     * Removes the first equivalent item found in the tree.
     * If item does not exist to be removed, throws IllegalArgumentException().
     */
    public void remove(E item) {
      this.root = remove(item, this.root);
    }
  
    private TreeNode&lt;E&gt; remove(E item, TreeNode&lt;E&gt; node) {
      if (node == null) {
        //didn't find item
        throw new IllegalArgumentException(item + " not found in tree.");
      }else if (item.compareTo(node.getData()) &lt; 0) {
        //go to left, saving resulting changes made to left tree
        node.setLeft(remove(item, node.getLeft()));
        return node;
      }else if (item.compareTo(node.getData()) &gt; 0) {
        //go to right, saving any resulting changes
        node.setRight(remove(item, node.getRight()));
        return node;
      }else {
        //found node to be removed!
        if (node.getLeft() == null &amp;&amp; node.getRight() == null) {
          //leaf node
          return null;
        }else if (node.getRight() == null) {
          //has only a left child
          return node.getLeft();
        }else if (node.getLeft() == null) {
          //has only a right child
          return node.getRight();
        }else {
          //two children, so replace the contents of this node with max of left tree
          E max = findMax(node.getLeft());  //get max value
          node.setLeft(remove(max, node.getLeft())); //and remove its node from tree
          node.setData(max);
          return node;
        }
      }
    }
  
    /** Returns the number of elements currently in this BST. */
    public int size() {
      return this.size;
    }
  
    /**
     * Returns a single-line representation of this BST's contents.
     * Specifically, this is a comma-separated list of all elements in their
     * natural Comparable ordering.  The list is surrounded by [] characters.
     */
    @Override
    public String toString() {
      return "[" + toString(this.root) + "]";
    }
  
    private String toString(TreeNode&lt;E&gt; n) {
      //would have been simpler to use Iterator... but not implemented yet.
      if (n == null) {
        return "";
      }else {
        String str = "";
        str += toString(n.getLeft());
        if (!str.isEmpty()) {
          str += ", ";
        }
        str += n.getData();
        if (n.getRight() != null) {
          str += ", ";
          str += toString(n.getRight());
        }
        return str;
      }
    }
  
      public String toFullString() {
          StringBuilder sb = new StringBuilder();
          toFullString(root, sb);
          return sb.toString();
      }
  
    /**
     * Preorder traversal of the tree that builds a string representation
     * in the given StringBuilder.
     * @param n root of subtree to be traversed
     * @param sb StringBuilder in which to create a string representation
     */
    private void toFullString(TreeNode&lt;E&gt; n, StringBuilder sb)
    {
  
      if (n == null)
      {
        return;
      }
  
  
  
  sb.append(n.getData().toString());
      sb.append("\n");
  
  
          if (n.getLeft() != null) {
          sb.append("&lt;");
      } else if (n.getRight() != null) {
          sb.append("&gt;");
      }
  
      if (n.getLeft() != null || n.getRight() != null)
      {
        toFullString(n.getLeft(), sb);   
        toFullString(n.getRight(), sb);
      }
    }
  
  
    /**
     * Tests the BST.
     */  
      public static void main(String[] args) {
      Collection collection = new ArrayList();
      collection.add(15);
      collection.add(12);
      collection.add(18);
      collection.add(10);
      collection.add(16);
      collection.add(20);
      collection.add(11);
      collection.add(17);
      BinarySearchTree bst = new BinarySearchTree(collection);
      //System.out.println(bst);      
      String temp = bst.toFullString();
      System.out.println(temp);
      }
  }
  </code></pre>
  
  <p>Any help with the recursive toFullString method will be greatly appreciated.</p>