CODEWITHSUNDEEP
javatree
User1000547
User1000547

Reputation: 4311

Inserting into a Tree

EDIT: proper solution:

void add(Student s)
{
    if(root == null)
        root = new TreeNode(s);
    else
        insert(root,s);        
}

void insert(TreeNode tn, Student s)
{
    if(tn.sVal.compareTo(s) > 0)
    {
        if(tn.left != null)
            insert(tn.left, s);            
        else
        {
            tn.left = new TreeNode(s);
            tn.left.parent = tn;
        }
    }
    else if(tn.sVal.compareTo(s) < 0)
    {
        if(tn.right != null)
            insert(tn.right, s);
        else
        {
            tn.right = new TreeNode(s);
            tn.right.parent = tn;
        }
    }
    balance(tn);
}

I'm trying to inserting to a binary tree using the following:

void add(Student s)
    {
        insert(root,s);
    }

private void insert(TreeNode t, Student s)
{        
    if(t == null)
        t = new TreeNode(s);        
    else if(t.sVal.compareTo(s) > 0)
        insert(t.right, s);
    else if(t.sVal.compareTo(s) < 0)
        insert(t.left,s);                
}

However, the tree remains empty, and I can't figure out why. I hate to be so vague, but I can't find an error in the logic. What am I missing?

Upvotes: 0

Views: 1807

Answers (3)

xikkub
xikkub

Reputation: 1660

It's a pointer issue. When you redefine pointer a using the = operator, all previous references to a are lost. In order to keep these references, you either have to change the object using member functions (class methods in Java) or write code to directly fix the references.

Put simply, redefining a pointer affects only that pointer. Anything which already references the pointer will not be updated.

Pseudocode Example:

Node a = new Node("hello")
Node b = a
a = new Node("goodbye")

print(a) // this prints "goodbye"
print(b) // this prints "hello"

In order for b to point to the new a, you must write b = a.

Having sorted that out, you will need to rewrite your insert() method. Because a tree is recursive, a recursive insert() method should do the trick. There are a variety of resources online for recursive tree implementations if you need them: Recursive Tree Java

Upvotes: 0

Bohemian
Bohemian

Reputation: 425298

Here's a big hint: Make this change first, then debug from there:

if (t == null)
    throw new IllegalArgumentException();

And a still bigger hint: When you create the new node, you must also have a reference to its parent so you can add it to the parent.

Upvotes: 3

Sam DeHaan
Sam DeHaan

Reputation: 10325

Your code is showing a basic misunderstanding of Java, and I'll try to help you understand where you're going wrong.

When you call insert(root,s), you're passing a reference to the same TreeNode object pointed to by root. When you then assign t = new TreeNode(s) inside the insert function, you are assigning a new reference to t, NOT to root.

Java is pass-by-value, and in the case of objects, that means it is passing the value of the reference. If you know C, you can think of it as a pointer. It is passing the memory address, not passing the pointer that points to the memory address.

Upvotes: 2

Related Questions