I am trying to visually print out a simple binary tree in Java. Here is the full code:
class WordPoint {
private final String word;
private final float pointValue;
public WordPoint(String w, float pw) {
this.word = w;
this.pointValue = pw;
}
public String getWord() {
return word;
}
public float getPointValue() {
return pointValue;
}
@Override
public String toString() {
return "(" + word + ", " + pointValue + ")";
}
}
class BinarySearchTree {
private Node root;
static class Node {
WordPoint data;
Node left;
Node right;
Node(WordPoint data) {
this.data = data;
}
}
// Method to insert a new WortPoint into the tree
public void insert(WordPoint wp) {
root = insertRec(root, wp);
}
private Node insertRec(Node root, WordPoint wp) {
if (root == null) {
return new Node(wp);
}
if(wp.getWord().charAt(0) < root.data.getWord().charAt(0)) {
root.left = insertRec(root.left, wp);
} else if (wp.getWord().charAt(0) > root.data.getWord().charAt(0)) {
root.right = insertRec(root.right, wp);
}
return root;
}
public void traversePreOrder(StringBuilder sb, String padding, String pointer, Node node) {
if (node != null) {
sb.append(padding);
sb.append(pointer);
sb.append(node.data.getWord());
sb.append("(").append(node.data.getPointValue()).append(")");
sb.append("\n");
StringBuilder paddingBuilder = new StringBuilder(padding);
paddingBuilder.append("| ");
String paddingForBoth = paddingBuilder.toString();
String pointerForRight = "+--";
String pointerForLeft = (node.right != null) ? "|--" : "+--";
traversePreOrder(sb, paddingForBoth, pointerForLeft, node.left);
traversePreOrder(sb, paddingForBoth, pointerForRight, node.right);
}
}
public void print(PrintStream os) {
StringBuilder sb = new StringBuilder();
traversePreOrder(sb, "", "", this.root);
os.print(sb.toString());
}
}
public class binaryTreeTest{
public static void main(String[] args) {
BinarySearchTree wordTree = new BinarySearchTree();
// Example words with their points
wordTree.insert(new WordPoint("copy", 5.2f));
wordTree.insert(new WordPoint("friend", 7.76f));
wordTree.insert(new WordPoint("end", 4.94f));
wordTree.insert(new WordPoint("apple", 6.34f));
wordTree.insert(new WordPoint("baseball", 5.64f));
wordTree.insert(new WordPoint("happy", 7.7f));
wordTree.insert(new WordPoint("fine", 3.46f));
wordTree.insert(new WordPoint("spam", 2.94f));
wordTree.insert(new WordPoint("laugh", 7.84f));
wordTree.insert(new WordPoint("new", 3.24f));
wordTree.insert(new WordPoint("school", 7.76f));
wordTree.insert(new WordPoint("unicorn", 7.82f));
System.out.println();
wortBaum.print(System.out);
System.out.println();
}
}
Here is my output:
copy(5.2)
| |--friend(7.76)
| | |--end(4.94)
| | | +--apple(6.34)
| | | | +--baseball(5.64)
| | +--happy(7.7)
| +--spam(2.94)
| | |--laugh(7.84)
| | | +--new(3.24)
| | +--unicorn(7.82)
Expected Output:
copy(5.2)
| |--friend(7.76)
| | |--end(4.94)
| | | |--apple(6.34) //here the "|" character is incorrect in my output
| | | | +--baseball(5.64)
| | | +--fine(3.46) // this one is missing in my output
| | +--happy(7.7)
| +--spam(2.94)
| | |--laugh(7.84)
| | | +--new(3.24)
| | | | +--school(7.76) // this one is missing in my output
| | |
| | +--unicorn(7.82)
The overall structure works. Its just that the last nodes in the tree are missing. Does anybody have an idea why?
I tried printing out the values regularly in form of regular lines and it worked. But doing it visually does not work at all.
I believe the problem is that when you InsertRec, you only check if the first letter is bigger or smaller, so when the first letter is the same but the word is different, it doesn't create new node. I would recommend checking the full word like that:
private Node insertRec(Node root, WordPoint wp) {
if (root == null) {
return new Node(wp);
}
int comparison = wp.getWord().compareTo(root.data.getWord());
if (comparison < 0) {
root.left = insertRec(root.left, wp);
} else if (comparison > 0) {
root.right = insertRec(root.right, wp);
}
return root;