//C++ code BSTY::BSTY() { root = NULL; } // You write: insert a new node with da
ID: 3716576 • Letter: #
Question
//C++ code
BSTY::BSTY() {
root = NULL;
}
// You write: insert a new node with data x (a string) into the
// binary search tree
// This method should return true if a new node is inserted and
// false if the data x is already in the tree
// Remember to check whether the new node will be the root
// (meaning the root is currently NULL) and if so, set the root
// to be the new node.
// Note: Make sure you make the new node point to its parent!!!
// Note2: after you've inserted a new node, you should call the
// adjustHeights method that will update the heights of all the
// ancestors of the node that was just inserted.
bool BSTY:: insertit(string x ) {
}
Explanation / Answer
// Lets assume the structure of Ndoe class is :
class Node
{
public:
string key;
Node node *left, *right;
};
// Lets Node *root is the root node of BSTY class
BSTY::BSTY() {
root = NULL;
}
// You write: insert a new node with data x (a string) into the
// binary search tree
// This method should return true if a new node is inserted and
// false if the data x is already in the tree
// Remember to check whether the new node will be the root
// (meaning the root is currently NULL) and if so, set the root
// to be the new node.
// Note: Make sure you make the new node point to its parent!!!
// Note2: after you've inserted a new node, you should call the
// adjustHeights method that will update the heights of all the
// ancestors of the node that was just inserted.
// Helper function
bool BSTY:: insertit(Node *node, string x, bool &status ) {
/* If the tree is empty, return a new node */
if (node == NULL){
Node *newNode = new Node;
newNode->key = x;
newNode->left = NULL;
newNode->right = NULL;
status = true;
return newNode;
}
if(node->key == x) {
status = false;
return node;
}
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
bool BSTY:: insertit(string x ) {
insert(root, x); // calling helper function
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.