18. Binary Tree: Subtracting nodes

Example: subtracting a node

The binary search tree formed in the last example is shown below

Task: Sam is removed from the tree, re-form the binary search tree.

Answer: There are two ways of doing this, both are correct. It just depends on the way the tree is examined by the software. The 'REMOVE' algorithm of the software might favour the left sub-tree or the right sub-tree as explained below.

Step 1: Remove the sam node. This leaves unconnected sub-trees

ALTERNATIVE 1

Step 2: Take the unconnected left node and attach it to the parent, which happens to be the root node in this case. So it now looks like

This still leaves the right sub-tree stranded, so apply the binary search tree rule once again. Tom is later than larry, so attach is to the right node of larry. Like this:

ALTERNATIVE 2

Instead of connecting the stranded left node, connect the stranded right node to the parent. Now apply the binary search tree rule to the left sub-tree containing larry, so in this case the tree looks like:

The new tree has now been formed, both Alternative 1 and Alternative 2 are correct binary trees.