# 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.

Copyright © www.teach-ict.com