Pseudo Code and conditions for deleting a Node in Binary Search Tree

Question

I'm trying to write a function to remove a node from a binary tree. I haven't coded the function yet, and I am trying to think about the different conditions I should consider for removing a node. I am guessing that the possible conditions are:

1. The node has no children

2. The node has one child

3. The node has 2 children

In each of these cases what would be the algorithm to perform a delete function?

Answer 1

This is something you would find in any standard textbook about algorithms, but let's suppose you are interested in the unbalanced case (balanced trees usually performs some rebalancing operations called "rotations" after a removal) and you use the "obvious" datastructure (a tree_node structure that holds the value and two pointers to other tree_node):

1. No children: release the memory hold by the node and set the parent's child link that pointed to it as NULL;
2. One child: release the memory hold by the node and set the parent's child link that pointed to it as the address of its unique child;
3. Two children: this is indeed the "complicated" case. Find the rightmost node of the left child (or the leftmost node of the right child), take its value, remove it (it is "case 1", so it is easy and can be done recursively) and set the current node's value as the one of that node. This is O(tree_height) = O(n), but it is not a problem (at least in theory) because this would be neverthless the complexity of finding a node.