Question

The following question uses Java and includes a template at the bottom. Here are the instructions:

Insert into a Binary Tree

• Binary Tree Insert works EXACTLY like a search, except you will find a value of -1 when an empty Node is found
• The object reference bintree contains a variable root which is a binary tree Node reference
• A Node object reference contains accessible variables: value left right
• Use the Node object reference variable thecurrent to search the tree
• Write a while loop to search for place to insert the value in the variable key
• Write an if-else to change the variable thecurrent to search the left or right child
• Initialize before the loop and change the variable thecurrent during the search
• When the loop completes assign the value of key to the object found that currently contains the value -1
• Do not declare/create/initialize bintree, Node or key

Template:

Node ??   =   ??? ;   // start the search/insert here
while (    ) {
if ( ) {

}
else {

}
}

Answer 1

// Java code to Insert the key into the Binary Tree

Node thecurrent  = bintree.root; // initialize thecurrent to the root of the binary tree
// loop that continues until we get a node with value -1
while(thecurrent.value != -1) {
   // if value of thecurrent >= key, insert the key in the left subtree
   if(thecurrent.value >= key){
       thecurrent = thecurrent.left;
   }  
   else // value of thecurrent < key , insert key in the right subtree
   {
       thecurrent = thecurrent.right;
   }  
}
// set the value of thecurrent to key
thecurrent.value = key;