What would happen if we wanted to remove node 40 from the tree below?

Since node 40 has two children, we can’t simply point to its child and hope it works. There’s an algorithmic approach to this problem too. The way we remove this node is by replacing it with the next largest value. How do we get the next largest value? By going into the right subtree, and then following the left subtree until we get to the leaf node.

Let’s look at that more closely.

We enter node 40’s right subtree.

We then follow the left subtree path until we get to a leaf node. So, we go to
node 43.

Since node 43 is a leaf node, we swap node 40 with node 43.

We can now remove node 40 from the tree.

If we examine the tree, we can see that the binary tree properties still hold. All nodes in the left subtree are smaller than the parent, and all nodes in the right subtree are larger than the parent. Just remember, to remove a node that has two children, start by looking in its right subtree. The node on the far left in its right subtree is the node that will replace the node you’re trying to remove.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.