I have a C++ question about deleting binary search tree. I am trying to delete t
ID: 3822585 • Letter: I
Question
I have a C++ question about deleting binary search tree. I am trying to delete the whole binary search tree ( every node in the tree), which one of these functions do you think will work better?
.....................................................................
Can you also please check and see if my insert function is correct? I am trying to insert string nodes into binary search tree without using any recrusion.
Node* GetNewNode(string data){
Node* newNode = new Node();
newNode->value=data;
newNode->left = newNode->right = NULL;
return root;
}
void insert(string word)
{
Node* current= root;
if(current == NULL)
{
root = GetNewNode(word);
}
else
while(current != NULL){
if(current->value.compare(word)<0)
current=current->left;
else
current=current->right;
}
}
Explanation / Answer
Hi, Please find my implementation.
Please let me know in case of any issue.
You can delete tree in post order fashion.
First delete lest and right subtree than delete root.
\ or should i use the following:
void destroyTree (Node*& tree) {
if (tree == NULL) return;
/* first delete both subtrees */
deleteTree(tree->left);
deleteTree(tree->right);
/* then delete the tree */
delete tree;
}
void insert(string word){
Node *ptr;
Node *ptr_parent;
if(root == NULL)
{//The BST is Empty...
Node *newNode = new Node;
newNode -> value = value;
newNode -> left = NULL;
newNode -> right = NULL;
root = newNode;
ptr = root;
} else { //traversing the tree to find the insertion point
ptr = root;
while(ptr != NULL)
{
if((ptr -> value) == value) {return false;} //to check for duplicates
if(value < (ptr -> value))
{
ptr_parent = ptr;
ptr = ptr -> left;
} else {
ptr_parent = ptr;
ptr = ptr -> right;
}
}
Node *newNode = new Node;
newNode -> value = value;
newNode -> left = NULL;
newNode -> right = NULL;
//checking for parent value to determine if
//the Node is a left or right child
if(value < (ptr_parent -> value))
ptr_parent -> left = newNode;
else
ptr_parent -> right = newNode;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.