String representation of a binary search tree

Question

I am trying to write a recursive string method for a binary search tree that returns a multi-line representation of a tree with information about the pre-order path.

Each node must be preceded by a series of <and> characters showing the path leading from the root to this node. I am not sure how to use the string prefix parameter, which expands with one character with each subsequent call.

The method should be able to reproduce this example:

Wood:

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

Expected printout:

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

I am new to recursion, and so far my actual print output has not been sufficiently closed after several hours of working with the code:

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

Here is my tree node class that works correctly:

 /** * 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 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 is my binary search tree class with the toFullString () method below:

 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 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 a recursive toFullString method is appreciated.

Answer 1

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

• How do I handle the current element in recursion?
• How to move from this element to the next, and what information is transmitted?

As we print each item in the tree, there will be one print statement inside each recursive call. However, the line printed on each line contains information about the previous steps that have been taken to reach the current node. How do we deal with this information? It must be passed from previous recursive calls to the next.

Here is a set of possible rules:

• If the current item is a sheet, print the current result.
• If the current element has a left node, add < and recursively act on the left node.
• If the current element has the right node, add > and recursively act on the right node.

What do we add < and > to? We need a parameter to carry over the current previous steps that occurred in the recursion from recursive call to call. You do not want to simply print < and > while traversing the tree, because you need to remember the current set of steps for printing the prefix for each node. There may be a second helper method that takes the same parameters as the original toFullString() , but a custom third parameter to wrap the current set of previous steps.

So the logic might look something like this:

• If the current prefix is ​​missing, initialize the prefix "" , since the root has no steps to reach it.
• If the current node is a leaf, add an output line with the current prefix + leaf value.
• If the current node has a left node, call toFullString() on the left of the node recursively and add < to the current prefix line that is passed.
• If the current node has the right node, recursively call toFullString() on the right of the node and add > to the current prefix line that is passed.