Recursive Insert for Binary Tree

Question

I'm working on code for insertion into a binary search tree. It works for the first node I insert, making it the root, but after that it doesn't seem to insert any nodes. I'm sure it's a problem with setting left/right references, but I can't quite figure it out. Please help!

    //params: key of node to be inserted, parent node
    public void insert(int newKey, TreeNode parent){

    //if the root of the tree is empty, insert at root
    if(this.getRoot() == null){
        this.root = new TreeNode(newKey, null, null);
    }

    //if the node is null, insert at this node
    else if(parent == null)
        parent = new TreeNode(newKey, null, null);


    else{
        //if the value is less than the value of the current node, call insert on the node's left child
        if(newKey < parent.getKey()) {
                insert(newKey, parent.getLeft());
        }
        //greater than value of current node, call insert on node's right child
        else if(newKey > parent.getKey()){
                insert(newKey, parent.getRight());
        }
        //same as value of current node, increment iteration field by one
        else if(newKey == parent.getKey())
            parent.incrementIterations();
    }

}

My treenodes have key, left, right, and iteration fields, as well as getter/setter functions. Thank you in advance!

One problem I can see is that parent is passed by value. Changes to parent will be to a local copy. You probably need to pass by reference. — Andrew W. Phillips
– Andrew W. Phillips, Commented Oct 9, 2014 at 4:20
Yes, thank you! I noticed that as well as added extra if loops to solve it. I believe this fixes the problem: if(newKey < parent.getKey()) { if(parent.getLeft() == null) parent.setLeft(new TreeNode(newKey, null, null)); else insert(newKey, parent.getLeft()); } I edited the code to check the parent node's children before recursively calling insert again and this allowed the parent node's left/right references to be set correctly. — Jenna Han
– Jenna Han, Commented Oct 9, 2014 at 4:29

user892871 · Accepted Answer · 2014-10-09 04:37:22Z

10

public Node insertNode(Node head, int data) {

        if(head == null){
            head = new Node();
            head.data = data;
            return head;
        }
        if(head.data < data) {
            head.right = insertNode(head.right,data);
        } else {
            head.left = insertNode(head.left, data);
        }
        return head;
    }

answered Oct 9, 2014 at 4:37

user892871

1,0253 gold badges13 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ajay Karthik · Accepted Answer · 2014-10-09 04:31:38Z

2

If (parent==null) you are creating a node, but you are not associating it to tree back. Its just created and garbage collected.

You should be using insert (newkey, parent) then u still have handle to tree

answered Oct 9, 2014 at 4:31

Ajay Karthik

412 bronze badges

Comments

Soumadip Dey · Accepted Answer · 2021-06-06 05:58:49Z

1

private AVLNode insert(AVLNode root, int value){
    if (root == null) return new AVLNode(value);

    if(root.value > value)
        root.leftChild = insert(root.rightChild, value);
    else
        root.rightChild = insert(root.leftChild, value);

    return root;
}

answered Jun 6, 2021 at 5:58

Soumadip Dey

776 bronze badges

Collectives™ on Stack Overflow

Recursive Insert for Binary Tree

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related