CODEWITHSUNDEEP
javaalgorithmdata-structuresbinary-treebinary-search-tree
Gautam
Gautam

Reputation: 1155

Binary Search tree - insertion

You are given a pointer to the root of a binary search tree and a value to be inserted into the tree. Insert this value into its appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function.

I have given my code but one test case is not working. Here is my code:

static Node Insert(Node root,int value){
    Node d =root;
    Node q = new Node();
    q.left = null;
    q.right=null;
    q.data = value;
    while(true){
        if(value<d.data){
            if(d.left==null){d.left = q;
                           return root; }
            else{
                d= d.left ;
            }
        }
        else{
            if(value>d.data){
                if(d.right==null){d.right=q;
                                 return root;}
                else d = d.right;
            }
        }
    }
}

Upvotes: 2

Views: 740

Answers (1)

user4668606
user4668606

Reputation:

You're missing two cases: value == d.data and the empty tree.

value == d.data: In that case the tree won't be altered in any way, but your code won't break-off and end up in an infinite loop.

Simplest solution would be to insert these lines in the while-loop:

if(value == d.data)
    return root;

The case where the tree is empty is rather implementation-specific, so it's difficult to suggest any solution for this case.

Upvotes: 3

Related Questions