String Representation of Binary Search Tree

Question

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.

Each node should be prefaced by a series of < 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.

The method should be able reproduce this example:

Tree:

     15
    /  \
   12  18
  /   /  \
 10  16  20
   \   \
   11  17

Expected Print Output:

15
<12
<<10
<<>11
>18
><16
><>17
>>20

I'm new to recursion and so far my actual print output isn't close enough after hours of messing with the code:

18
<17
<10
>15
<11
>12
16
20

Here's my tree node class that works properly:

/**
 * A single binary tree node.
 * <p>
 * Each node has both a left or right child, which can be null.
 */
public class TreeNode<E> {

  private E data;
  private TreeNode<E> left;
  private TreeNode<E> right;

  /**
   * Constructs a new node with the given data and references to the
   * given left and right nodes.
   */
  public TreeNode(E data, TreeNode<E> left, TreeNode<E> 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<E> getLeft() {
    return left;
  }

  /** Causes this Node to point to the given left child Node. */
  public void setLeft(TreeNode<E> left) {
    this.left = left;
  }

  /**
   * Returns this nodes right child.
   * If there is no right child, returns null.
   */
  public TreeNode<E> getRight() {
    return right;
  }

  /** Causes this Node to point to the given right child Node. */
  public void setRight(TreeNode<E> right) {
    this.right = right;
  }
}

Here's my binary search tree class with the toFullString() method near the bottom:

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<E extends Comparable<E>> {

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

  /** Creates an empty tree. */
  public BinarySearchTree() {
  }


    public BinarySearchTree(Collection<E> col) {
        List<E> list = new ArrayList<E>(col);
        Collections.shuffle(list);
        for (int i = 0; i < 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<E>(item);
    }else {
      //find where to insert, with pointer to parent node
      TreeNode<E> parent = null;
      TreeNode<E> curr = this.root;
      boolean wentLeft = true;
      while (curr != null) {  //will execute at least once
        parent = curr;
        if (item.compareTo(curr.getData()) <= 0) {
          curr = curr.getLeft();
          wentLeft = true;
        }else {
          curr = curr.getRight();
          wentLeft = false;
        }
      }

      //now add new node on appropriate side of parent
      curr = new TreeNode<E>(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<E> 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<E> node) {
    if (node == null) {
      return null;
    }else if (item.compareTo(node.getData()) < 0) {
      return get(item, node.getLeft());
    }else if (item.compareTo(node.getData()) > 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<E> remove(E item, TreeNode<E> node) {
    if (node == null) {
      //didn't find item
      throw new IllegalArgumentException(item + " not found in tree.");
    }else if (item.compareTo(node.getData()) < 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()) > 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 && 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<E> 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<E> n, StringBuilder sb)
  {

    if (n == null)
    {
      return;
    }



sb.append(n.getData().toString());
    sb.append("\n");


        if (n.getLeft() != null) {
        sb.append("<");
    } else if (n.getRight() != null) {
        sb.append(">");
    }

    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);
    }
}

Any help with the recursive toFullString method will be greatly appreciated.

Answer 1

There are two levels you need to think about when designing a recursive solution.

1. How do I deal with the current item in the recursion?
2. How do I go from this item to the next one, and what information gets passed on?

Since we are printing out each item in the tree, there is going to be a single print statement inside of each recursive call. However, the string printed in each row includes information about previous steps that were traversed to reach the current node. How do we deal with this information? It needs to be passed down from previous recursive calls to the next one.

Here is a set of possible rules:

1. If the current item is a leaf, print out the current result.
2. If the current item has a left node, add <, and recursively act on the left node.
3. If the current item has a right node, add >, and recursively act on the right node.

What do we add < and > to? We need a parameter to carry along the current previous steps that have occurred in the recursion from recursive call to call. You don't want to simply print out < and > as you traverse the tree, because you need to remember the current set of steps to print out the prefix to every single node. There could be a second helper method that takes the same parameters as the original toFullString(), but a custom third parameter to carry the current set of previous steps.

So the logic might look something like this:

• If there is no current prefix, initialize prefix to "", since the root initially has no steps to reach it.
• If the current node is a leaf, add a line of output with the current prefix + leaf value.
• If the current node has a left node, recursively call toFullString() on the left node, and add < to the current prefix string, which is handed down.
• If the current node has a right node, recursively call toFullString() on the right node, and add > to the current prefix string, which is handed down.