CODEWITHSUNDEEP
javaalgorithmtreebinary-search-tree
drBet
drBet

Reputation: 485

Java binary search tree - insert implementation

I have this problem with the implementation of the binary search tree insertion. Now I have tried it with both the recursive method, and the iterative as well. The way that I got so far is "okay at best" since for a tree size = 31609 and tree height = 35 the insertion takes about 100 seconds, and it is supposed to be WAAAAAAY lower around one second. Can somebody please give me a hint what I might be doing wrong?

Here is the code of what I have managed to do so far (Insertion without duplicates):

void insert(int val){
    if(this.elem < val){
        if(this.right != null){
            this.right.insert(val);
        }
        else{
            nodes++;
            this.right = new Node(val);
        }
    }
    else if(this.elem > val){
        if(this.left != null){
            this.left.insert(val);
        }
        else{
            nodes++;
            this.left = new Node(val);

        }
    }
    else {
        return;
    }
}

Upvotes: 4

Views: 393

Answers (1)

Ashkan Kazemi
Ashkan Kazemi

Reputation: 1097

if you use the function defined in line 270 for insertion, the long time is actually explainable.

look at this piece of code :

public void insert(int val) {

        if (root == null) {
            nodes++;
            root = new Node(val);
        } else if (!root.exists(val)) {
            root.insert(val);
        }

    }

this calls a function exists(), which is defined as follows:

boolean exists(int val) {
            return val == this.elem
                    || (val < this.elem ? (this.left != null && this.left.exists(val))
                            : (this.right != null && this.right.exists(val)));
        }

and as you see this piece of code, you can easily figure out that maybe each time you call this function, your code traverses the whole tree recursively! so if you do insertion 100K times, your code runs in O(n^2*logn) time at worst, so 100 seconds is actually a good running time!

I think what you have to do is modify your exists() function.

Upvotes: 1

Related Questions