data structures - Binary Search Tree in C: remove node function -

data structures - Binary Search Tree in C: remove node function -

i'm putting functions binary search tree , ran wall. i'm working on each situation might encountered when node holding specified value needs removed tree. i'm uncertain how handle freeing node if not have left , right child. function must homecoming node. up, examine each left , right child, , remove value while it's in child? if value in root, wouldn't have similar problem how remove it? way of explanation, programme uses void pointer casts type val in separate function compare() evaluates both values , returns -1 <, 0 ==, , 1 >.

struct node *_removenode(struct node *cur, type val) { if (compare(cur->val, val) == 0) { //if val == cur->val if (cur->right != null && cur->left != null) { //if cur has right , left cur = _leftmost(cur->right); free(_leftmost(cur->right)); } else if (cur->right == null && cur->left != null) { //if cur has left cur = cur->left; free(cur->left); } else if (cur->right != null && cur->left == null){ //if cur has right cur = cur->right; free(cur->right); } else if (cur->right == null && cur->left == null){ //if cur has no kid //free cur if cur = val } } else if (compare(cur->val, val) == -1) { cur->right = _removenode(cur->right, val); } else if (compare(cur->val, val) == 1) { cur->left = _removenode(cur->left, val); } homecoming cur; }

if node has neither kid can deleted. in order create recursion in other cases work, should homecoming null _removenode. in cases, cur should deleted (freed) no longer needed. in each case, need homecoming replacement subtree. complication occurs in first case left descendent of right kid pulled up. after pulling up, need remove right sub-tree (note may right sub-tree).

i wrote of below off top of head prepared few errors/a bit of debugging. also, _leftmost , _removeleftmost can merged bit of work.

the block in question should like:

node *replacement; if (cur->right != null && cur->left != null) { //if cur has right , left replacement = _leftmost(cur->right); replacement->right = _removeleftmost(cur->right,replacement); replacement->left = cur->left; } else if (cur->right == null && cur->left != null) { //if cur has left replacement = cur->left; } else if (cur->right != null && cur->left == null){ //if cur has right replacement = cur->right; } else if (cur->right == null && cur->left == null){ //if cur has no kid replacement = null; } free(cur); cur = replacement;

the function _removeleftmost walks downwards left kid pointers until sees node replaced , replaces right kid of node. like:

node *_removeleftmost(node, remove) { if (node == remove) { homecoming node->right; // note remove->left should null } else { node->left = _removeleftmost(node->left,remove); homecoming node; } }

also, main phone call like

root = _removenode(root, val);

so handles concern when node root.

c data-structures binary-search-tree