This Insert method recursively traverses the tree , similarly to the Exists method . The method also checks for duplicate values and returns false if a duplicate is found. Insert will always return true with the exception of when if finds a duplicate, implement insert method? c++

bool Bst::Exists(const int item, const Node *node) { // traverse the tree, starting a node, searching for the value held by // the parameter "item". Returns false if the value does not exist in // the tree, otherwise returns true. The parameters are made constant // to prevent the modification of them. A varient of this method was // given in class. if(node == 0) { return false; }

if(item < node->data) { return Exists(item, node->left); }

if(item > node->data) { return Exists(item, node->right); }

// return the comprison if there is no need to traverse or node != 00 return node->data == item; } // **********************************************************************************

// ********************************************************************************** // Methods below must be implmented. Insert(const int item) is already complete // All other methods must be completed. // **********************************************************************************

bool Bst::Insert(const int item) { // calls the recursive Insert method. Return true if the method returns true // otherwise false if(Insert(item, root)) { size += 1; return true; }

return false; }

bool Bst::Insert(const int item, Node *&node) { // a recursive method that traverses the tree and adds a new node to the tree when // the correct position is found. It returns false if a duplicate item is found, // otherwise returns true when it finds a position to insert the new node. // // There are several ways to perform this task, three are listed below: // 1. take advantage of the pointer-reference variable, traverse to and create the // new node at the position the node is supposed to be placed. Because the // pointer is also a reference, the pointer is essentially the parent's left // or right pointer. // 2. use two pointers, one to traverse to the position to place the node, and // the other, a trailing pointer that points to node just recently left (i.e., // the parent of the current node). This will allow access to the parent's // left or right pointer where you can assign the newly created node. // 3. before traversing left or right, look at the respective pointer to see if it // is (or is not) a null pointer. If it is a null pointer, you can create a new // node and assign the left/right pointer to the new node.

// *** implement this method ***

}