1 2 Previous Next 22 Replies Latest reply: Dec 6, 2007 11:47 AM by 807601

# BINARY TREE & RECURSIVE INSERT METHOD

I hav a final assignment for my second year at uni and i can't get it to work!
The assignment involves this code:
``````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;
for (;;)
{
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 QUESTION IS: Turn the insert method in class BST into a recursive one. You should pass the root to the method as follows.

public void insertR (BSTNode root, Comparable elem)

You would insert at the root if the tree is empty, otherwise you would insert in the left subtree if the element is smaller than the root element and in the right subtree if the element is larger than the root element.

• ###### 1. Re: BINARY TREE & RECURSIVE INSERT METHOD
kt21blonde wrote:
I hav a final assignment for my second year at uni and i can't get it to work!
...
Okay, that is just an almost exact copy of the code from:
which was poor to begin with.

Do you have some code of your own? If so, do you have a specific question other than "I can't get it to work", which isn't even a question.

Show some effort please! Right now you seem like just a lazy student and there are more than enough of those around here.
• ###### 2. Re: BINARY TREE & RECURSIVE INSERT METHOD
I've been trying this for the last six hours and a few hours yesterday, I'm far from a lazy student,I'm a good, hard worker who only struggles with java on my course :( yet i enjoy it... Ok, the code i completed in a seminar is as follows:
``````public class BST
{
private BSTNode root;

public static void main (String args[])
{
BST myTree = new BST ();
myTree.insert("lion"); // INSERTING ELEMENTS INTO THE TREE
myTree.insert("Fox");
myTree.insert("rat");
myTree.printInOrder(myTree.getRoot());// PRINTS THE ELEMENTS OF THE TREE
}                                                    // IN ALPHABETICAL ORDER.

public BST ()
{
// Construct an empty BST.
root = null; // STARTING THE ROOT OFF WITH A NULL VALUE
}

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;

for (;;)

{
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);
}
}
}``````
We have then been asked to turn the insert method into a recursive one as part of our homework assignment. Passing the root to the method as follows:

public void insertR (BSTNode root, Comparable elem)

Then insert at the root if the tree is empty, otherwise insert in the left subtree if the element is smaller than the root element and in the right subtree if the element is larger than the root element.

• ###### 3. Re: BINARY TREE & RECURSIVE INSERT METHOD
pseudocode
``````public void insertR (BSTNode root, Comparable elem)
{
if(mainroot is null)
{
set mainroot as root
return;
}

if(elem < root.elem)
if root.left is null
set root.left as elem
return;
else
insertR(root.left, elem)
else
if root.right is null
set root.right as elem
return
else
insertR(root.right, elem)
} ``````
• ###### 4. Re: BINARY TREE & RECURSIVE INSERT METHOD
Thanks very much for your reply, however that method is coming up with error

U:\DATA_STRUCTURES_YEAR_TWO\Homework3_BST\BST\BST.java:8: insertR(BST.BSTNode,java.lang.Comparable) in BST cannot be applied to (java.lang.String)
*          myTree.insertR("lion"); // INSERTING ELEMENTS INTO THE TREE*

Any suggestions? x
• ###### 5. Re: BINARY TREE & RECURSIVE INSERT METHOD
kt21blonde wrote:
Thanks very much for your reply, however that method is coming up with error

U:\DATA_STRUCTURES_YEAR_TWO\Homework3_BST\BST\BST.java:8: insertR(BST.BSTNode,java.lang.Comparable) in BST cannot be applied to (java.lang.String)
*          myTree.insertR("lion"); // INSERTING ELEMENTS INTO THE TREE*

Any suggestions? x
You are providing one parameter while there are two needed.
This is what you get when copy and pasting other people's code.
• ###### 6. Re: BINARY TREE & RECURSIVE INSERT METHOD
kt21blonde wrote:
... I'm far from a lazy student,I'm a good, hard worker ...
How can you say that while it is obvious that you copied the code from someone else*?
Christ, no, you are not lazy, you are an utter mor&#111;n!

• ###### 7. Re: BINARY TREE & RECURSIVE INSERT METHOD
A moron?? just because I wasnt born with the ability to do java from the top of my head! I came on here for help, not to be insulted! If you didn't know the answer, you only had to say! If anyone other than an asshole has any help for my problem, it would be much appreciated! The code is copied directly from my assignment which has obviously been used at various universities! :D xx
• ###### 8. Re: BINARY TREE & RECURSIVE INSERT METHOD
kt21blonde wrote:
A moron?? just because I wasnt born with the ability to do java from the top of my head!
No one is born with that ability. You are an utter mor&#111;n, because you stole the code from someone else. This is called plagiarism and is a serious offense!
\\
\\
...
If anyone other than an asshole has any help for my problem, it would be much appreciated! The code is copied directly from my assignment which has obviously been used at various universities! :D xx
I don't believe that such a bad implementation is handed out by a teacher. I do believe the skeleton might be the same, but it is obvious that you copy and pasted it from the link I posted earlier. You even posted in that same thread you stole the code from!
• ###### 9. Re: BINARY TREE & RECURSIVE INSERT METHOD
OK, here is the code I completed myself after being given a skeleton by our tutor:
``````public class BST
{
private BSTNode root;

public static void main (String args[])
{
BST myTree = new BST ();
myTree.insert("lion"); // INSERTING ELEMENTS INTO THE TREE
myTree.insert("Fox");
myTree.insert("rat");
myTree.printInOrder(myTree.getRoot());// PRINTS THE ELEMENTS OF THE TREE
}                                                    // IN ALPHABETICAL ORDER.

public BST ()
{
// Construct an empty BST.
root = null; // STARTING THE ROOT OFF WITH A NULL VALUE
}

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;

for (;;)

{
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);
}
}
}``````
This works and returns values in alphabetical order... all I'm after is code for the insertR method. I have struggled with this the last two days and I havent come on here to argue, just seeking answers!
• ###### 10. Re: BINARY TREE & RECURSIVE INSERT METHOD
It would help if you followed good coding practice. For a start look in your insert(), infinite loops are a bad idea. The code underneath it will never be executed and your program will never exit without intervention. Also, use proper indentation and have only one command per line.
``````left = null;
right = null;``````
not
``left = null;  right = null;``
Read through the pseudo code above carefully, think about how best to implement it and test it before posting again. I just hope for your sake you don't have to submit a plagerism report, any detection service would pick this up.
• ###### 11. Re: BINARY TREE & RECURSIVE INSERT METHOD
Thanks very much for your reply, however that method is coming up with error
That's because it's pseudocode...
java:8: insertR(BST.BSTNode,java.lang.Comparable) in BST cannot be applied to (java.lang.String)
THIS is the error that you get from using my code verbatim?! Pretty damn strange.
• ###### 12. Re: BINARY TREE & RECURSIVE INSERT METHOD
here is the code I completed myself after being given a skeleton by our tutor:
So you wrote 4 lines of a main method, and made no attempt to implement the recursive insert?
all I'm after is code for the insertR
That's your homework assignment, though... why don't you just try to implement the pseudocode I gave you?

If you understand at all what I tried to get across in that post, it should be fairly straightforward.

If you didn't understand it at all... maybe you should have studied more this quarter.
• ###### 13. Re: BINARY TREE & RECURSIVE INSERT METHOD
I appreciate your help with the pseudocode yet it didnt work after implementation and kept returning the same error each time I tried. I CAN NOT try any more in this module, I, like all of my other students in my group, am struggling with the intensity of data structures and algorithms at university. Not that I have to explain myself to anyone on this forum, I was simply seeking a kind hearted soul to assist me with the one method I found difficult and all I got in return was nagging and insults!

I'll know in future to avoid this forum to avoid intimidation and textual abuse, from what I have seen it is not only me who has been a victim to it!

Maybe you should get out more and meet REAL friends not those displayed on a LCD screen??
Maybe then you'l realise the importance of assistance and constructive advice.

Thank you.
• ###### 14. Re: BINARY TREE & RECURSIVE INSERT METHOD
Dont think our uni tought us about recursive methods. Anyway I got the program working. Post the recursive method with public void insertR (BSTNode root, Comparable elem) and I'll have a look.

Later.
1 2 Previous Next