Delete BST Node
// find minimum in a tree. Node* findMin(Node* root) { while(root->left != NULL) root = root->left; return root; } // delete a value from Binary Search tree. struct Node* delete(struct Node *root, int data) { if(root == NULL) { return root; } else if (data < root->data) { root->left = delete(root->left,data); } else if (data > root->data) { root->right = delete(root->right,data); } else { // found it if (root->left == NULL && root->right == NULL) { // case 1: No child delete root; root = NULL; } else if(root->left == NULL) { // case 2: One child struct Node *temp = root; root = root->right; delete temp; } else if(root->right == NULL) { struct Node *temp = root; root = root->left; delete temp; } else { // case 3: 2 children struct Node *temp = findMin(root->right); root->data = temp->data; // just change the value, no need to really change node links root->right = delete(root->right,temp->data);// reuse delete() itself, this time will be case 1 or 2 } } return root; }
page revision: 15, last edited: 30 Oct 2015 19:10