CODEWITHSUNDEEP
javatreebinary-tree
kiraleos
kiraleos

Reputation: 59

Java binary tree insert not making any changes to the tree

So I'm working on implementing an insert method for a binary tree.

From what I can tell, the problem is that the changes made in the arguments of the function don't get properly returned back to main().

static void addChild(Child c, Child tree){
    if(tree==null){
        tree=c;
    }
    else{
        if(c.cid>tree.cid){
            addChild(c, tree.lc);
        }
        else if(c.cid<tree.cid){
            addChild(c, tree.rc);
        }
    }
}

The Child objects seen above have nothing to do with the children of the nodes in the tree.

The tree nodes are Child objects.

cid is a field in the Child class which holds an integer.

rc is the right child of a node.

lc is the left child of a node.

Arguments of addChild:

@param Child c : the Child to insert into the tree

@param Child tree : the root of the tree

Basically my question is, shouldn't this be working correctly? When the method completes, the right child and left child of the tree given in the argument are null.

Upvotes: 3

Views: 178

Answers (2)

Alain O&#39;Dea
Alain O&#39;Dea

Reputation: 21686

Your recursive base case:

tree = c;

won't update the tree. It just reassigns the tree parameter's reference in that call scope. It has no effect outside that particular recursive call (stack frame).

Here's a walk through of execution:

Child tree = new Child();
tree.cid = 0;
tree.lc = new Child();
tree.lc.cid = 1;
Child c = new Child();
c.cid = 2;
addChild(c, tree);
    // tree != null
    // c.cid>tree.cid
    addTree(c, tree.lc);
        // tree != null
        // c.cid>tree.cid
        addTree(c, tree.lc);
            // tree == null
            tree = c; // Won't be effective
        return;
    return;

That locally mutates the tree reference and has no effect outside this recursive call.

The trick here is to update the parent tree's left or right subtree at this point.

static Child addChild(Child c, Child tree){
    if(tree==null){
        return c;
    }
    else{
        if(c.cid>tree.cid){
            tree.lc = addChild(c, tree.lc);
        }
        else if(c.cid<tree.cid){
            tree.rc = addChild(c, tree.rc);
        }
        return tree;
    }
}

Tracing the new version looks like:

Child tree = new Child();
tree.cid = 0;
tree.lc = new Child();
tree.lc.cid = 1;
Child c = new Child();
c.cid = 2;
addChild(c, tree);
    // tree != null
    // c.cid>tree.cid
    tree.lc = addTree(c, tree.lc);
        // tree != null
        // c.cid>tree.cid
        tree.lc = addTree(c, tree.lc);
            // tree == null
            return c;
        return tree;
    return tree;

Upvotes: 0

Electrix
Electrix

Reputation: 520

The recursive method only modifies the local copy on the stack.. Instead you should be passing a pointer or pass a reference to the tree nodes so that when u assign a child in the base case you make changes to the actual parent and not to the local copy (local copy gets destroyed after the function returns)

Upvotes: 3

Related Questions