It has been some time since I wrote first part of BST tutorial and now it is time go publish second part. In this second part we shall first discuss how algorithm for removal of certain value/node from BST works and in third and last part of this series we shall conclude whole thing with implementation example. Code that I shall present in this third article might not be optimal but I shall give my best to enhance it over time, for sure it will be good enough to understand implementation of algorithm for removal of value/node in BST. Also I shall rely on the code that was implemented in first part of this tutorial series.
First of all lets see how algorithm actually works. For sure first step of the algorithm is to find the position of the node that we want to remove, from that step there are tree options that we need to consider in order to successfully remove positioned node, let’s see those tree cases looking from the perspective of located node for removal:
- In case node for removal is leaf (does not have a child nodes) – it is enough to remove this node from the tree by setting parent left or right node to null (depending if node for removal was a left or right node of a parent)
- In case node for removal has only one child – simply positioned node’s child takes place of node for removal
- In case node for removal has both children – this is most complex part of the algorithm, first we need to look for the node with minimum value in right sub-tree of node for removal (node with minimal value is leftmost node in the sub-tree), after we determine node with minimal value in the right sub-tree we need to set that node to be in place of node that we want to remove.
Now let’s see for all these cases described above, how algorithm works for one example of a tree
For the case when node for removal has no children we shall take out node with value 8:
This is simple and straight forward, first we locate node with value 8 in the binary tree and simply set right child of node with value 5 to null.
For second case when we want to remove node that has only one child, on same starting binary tree, we shall take out node with value 14:
For this second case, first we position in the tree node with value 14, than we take it’s left child node and make it to be a left child of node with value 16 (parent node of a node with value 14).
And now the most complicated case, we consider to take out node with value 19 from a starting binary tree:
First step, as always, is to identify node with value 19 and then second step is to find node with minimal value in right sub-tree of node with value 19, in this case we can apply algorithm for finding minimal value (described in first part of this article series) and then removing this value from sub-tree using recursion of this algorithm.
Finally references of a parent node and references to child nodes of node with value 19 needs to be updated, first node with value 21 must point to the children nodes with value 17 and 29 and parent node with value 16 to point to node with value 21, at the end set pointers for children nodes of node with value 19 to null.
So this is end of part 2 for BST, I hope that everything explained is clear, in case you have comments or there is something unclear, please leave comment below and I shall be glad to reply back.
I shall try to publish third part of this article series soon, where we shall see Java implementation of algorithm explained above. Have a nice day …