Create Binary Tree From A String Of Letters

Here is the problem:

Start with the tree.java program (Listing 8.1) and modify it to create a binary tree from a string of letters (like A, B, and so on) entered by the user. Each letter will be displayed in its own node. Construct the tree so that all the nodes that contain letters are leaves. Parent nodes can contain some non-letter symbol like +. Make sure that every parent node has exactly two children. Don’t worry if the tree is unbalanced. Note that this will not be a search tree; there’s no quick way to find a given node. You may end up with something like this:

It also says all Letters must be Leaves

Now I had it almost similar to that picture, but it wasn't right. So ive been working on it but im getting some very strange (and frustrating) output from the following methods.

Ive included the display method just for reference. The book told me to use it so I haven't edited it. I believe my main issue is with my (incomplete) insert() method. The output goes into an infinite loop despite having a return statement break the while loop when a character is inserted.

The way I see to solve the problem is just add a (+) whenever a new subtree needs to be created. Say I add A and B, then it first creates a subtree at the root with a (+) and afterwards lists A and B as its leaves. If I insert a C, it should be able to simply move to the right child of the root and deposit the C there.

package pkg4333_hwk1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

class Main {

[Code] ....