Binary search tree recursive insert method
807600Dec 4 2007 — edited Dec 6 2007Hi i am strugeling on an assignment i have been given and would greatly appreciate any help
the question is to change the insert method in the piece of code below to a recursive version
///------------------------------------------------------------------------------------
public class BST
{
private BSTNode root;
public BST ()
{
// Construct an empty BST.
root = null;
}
public class BSTNode
{
// BSTNode constructor, sets up Node containing elem and two null links
protected Comparable element;
protected BSTNode left, right;
protected BSTNode (Comparable elem)
{
element = elem;
left = null; right = null;
}
}
public BSTNode getRoot()
{
// return the root of the tree
return root;
}
public void insert (Comparable elem)
{
// insert an elem into the tree
int direction = 0;
BSTNode parent = null, curr = root;
while(true)
{
if (curr == null)
{
BSTNode ins = new BSTNode(elem);
if (root == null) root = ins;
else if (direction < 0)
parent.left = ins;
else parent.right = ins;
return;
}
direction = elem.compareTo(curr.element);
if (direction == 0) return;
parent = curr;
if (direction < 0) curr = curr.left;
else curr = curr.right;
}
}
public void printInOrder (BSTNode root)
{
// Print, in ascending order, all the elements in the BST subtree
// whose topmost node is root.
if (root != null)
{
printInOrder(root.left);
System.out.println(root.element);
printInOrder(root.right);
}
}
}
//---------------------------------------------------------------------------------
the dirver class i am using is:
//-----------------------------------------------------------------------------------
public class driverBST
{
public static void main (String args[])
{
BST BST1 = new BST();
BST1.insert(BST1.getRoot(),"lion");
BST1.insert(BST1.getRoot(),"fox");
BST1.insert(BST1.getRoot(),"rat");
BST1.insert(BST1.getRoot(),"cat");
BST1.printInOrder(BST1.getRoot());
BST BST2 = new BST();
BST2.insert(BST2.getRoot(),"one");
BST2.insert(BST2.getRoot(),"two");
BST2.insert(BST2.getRoot(),"three");
BST2.insert(BST2.getRoot(),"four");
BST2.insert(BST2.getRoot(),"five");
BST2.insert(BST2.getRoot(),"six");
BST2.insert(BST2.getRoot(),"seven");
BST2.insert(BST2.getRoot(),"eight");
BST2.insert(BST2.getRoot(),"nine");
BST2.insert(BST2.getRoot(),"ten");
BST2.printInOrder(BST2.getRoot());
}
}
//-------------------------------------------------------------------------------
so far i have changed the insert method so it now looks like this below but it is not working i get no results when i print it to the screen.
//-----------------------------------------------------------------------------------
public BSTNode insert (BSTNode top,
Comparable elem)
{
// Insert the element elem in the subtree whose topmost node is top.
// Return a link to the modified subtree.
if (top == null) {
return new BSTNode(elem);
} else {
int comp = elem.compareTo(top.element);
if (comp < 0)
top.left = insert(top.left, elem);
else if (comp > 0)
top.right = insert(top.right, elem);
}
return top;
}