Java/Groovy Binary Tree Insertion

Question

I am trying to write a binary tree recursive insertion and I not getting anywhere for last hours. I either get a stackoverflow error or not all items are being inserted.

I want to insert these values in my tree:

binaryTree.addNodeRecursion(new MNode(50, "fourth"))
binaryTree.addNodeRecursion(new MNode(25, "third"))
binaryTree.addNodeRecursion(new MNode(15, "second"))
binaryTree.addNodeRecursion(new MNode(10, "first"))
binaryTree.addNodeRecursion(new MNode(75, "fifth"))
binaryTree.addNodeRecursion(new MNode(85, "sixth"))

I want to do this without passing the root around as a parameter. So my code looks like this:

   public void addNodeRecursion(MNode newNode){

        if(root == null) {
            root = newNode
        }else{
            addRecurs(newNode); //this is the recursive function, it should not return a node object
        }
    }

Note, that I am not talking about a Binary Search Tree but a Binary tree, where elements order is not relevant. I care about how elements are inserted. I want to insert them as it is show below:

1 Step: 
            50

2 Step:
            50
           /
          25

3 Step:
            50
           /  \
          25  15

4 Step:
            50
           /  \
          25  15
         /
        10

5 Step:
            50
           /  \
          25  15
         /  \
        10  75

6 Step: (now notice that I am going back to the sibling of the current parent)

             50
           /   \
          25    15
         /  \   /
        10  75 85

Now here is my addRecurs function:

private void addRecurs(MNode newNode) {

    if(newNode == null) { return };

    if(root.leftNode == null){ //Step 2 if the left node is null assign it
        root.leftNode = newNode 
    }else{ //Else that means the right Node is null
        root.rightNode = newNode // Step 3 set the right node
        root = root.leftNode // the the parent to the left node
        addRecurs(newNode) // repeat
    }

};

It doesn't work.

Can this be done without tracking or storing the parent in a variable?

DO you have a simple complete example that shows your problem? — tim_yates
– tim_yates, Commented Jul 20, 2015 at 16:00
No, this is just something I am trying to do in my free time. I came up with the problem myself and trying to solve it. The main issue is that I want to insert elements in a specific order as I showed with the steps — Trt Trt
– Trt Trt, Commented Jul 20, 2015 at 16:02

blackdrag · Accepted Answer · 2015-07-20 17:53:59Z

1

I would suggest you back your tree by a something like a Heap. Basically a tree structure based on an array, you seem not to need the sorting part, so it is very simple. For a better answer we would need more information

answered Jul 20, 2015 at 17:53

blackdrag

6,5382 gold badges30 silver badges40 bronze badges

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

Comments

Community · Accepted Answer · 2017-05-23 10:24:19Z

0

Your question is answer over here.

static void addNode(node n)
{
    if(root==null)
    {
        root = n;
    }
    else
    {
        node tmp = root; // save the current root
        if(root.getValue()>n.getValue())
        {
            root = root.leftLink;
            addNode(n);
        }
        else if(root.getValue()<n.getValue())
        {
            root = root.rightLink;
            addNode(n);
        }
        root = tmp; // put the root back to its original value
    }
    return;
}

edited May 23, 2017 at 10:24

CommunityBot

11 silver badge

answered Jul 20, 2015 at 18:03

Zaid Qureshi

1,2331 gold badge10 silver badges15 bronze badges

1 Comment

Trt Trt Over a year ago

This is the thing. The guy here uses comparison. I just enter my values without comparing. Removing the if in that code will not work.

Collectives™ on Stack Overflow

Java/Groovy Binary Tree Insertion

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related