• How would you delete a node from a binary tree?

This question is deceptively similar to inserting a node in a binary tree, however insertion in a binary tree is very trivial similar to insertion in a linked list. Deleting a node in a binary tree is tricky as you would have to take care of the ordering of the nodes in a binary tree. It's a bit trickier than deletion in a linked list as we have to take care of different cases. Let's consider the following tree for our purposes.

You might start out with the simplest case i.e. deleting a leaf node. In our case the leaf nodes are 1,3, 5 and 7. Deleting any one of them should be trivial as you just make either the right child or left child pointer of the deleted node's parent NULL.

The tricky part comes when you try to delete a node which is NOT a leaf node. Say you want to delete node numbered 6. In that case you are obliged to replace node numbered 6 with another node which would be greater than 4 and less than 7. That is possible with node numbered 5. This sort of gives you a hint about which node to pick as replacement when you delete a non-leaf node.

In our case, we just picked the left child of the deleted node. Let's further investigate this thought. What if we delete 4, will it's left child do the job as the new root of the tree? Obviously not since 3 would occur in the left branch of a tree with root as 2.

So what we really need to do when deleting a node that has both a left and a right child is to replace that node with another node which is less than all the numbers in the right branch of the subtree rooted at the node that we intend to delete and is greater than all the nodes in left branch of the subtree rooted at the node that we intend to delete.

Note that in our example tree the nodes 3 or 5 can be replaced in place of 4. This gives away the general pattern hidden in deleting a non-leaf node with both a right and left child. Replace that the deleted node with either the leftmost child of it's right subtree or the rightmost child of it's left subtree. Either of this node would suffice the conditions mentioned earlier and can be used.

One last case still needs to be taken care of. What if a tree is not balanced and the node being deleted doesn't have a left child. This case also proves to be trivial as in such a case we just replace the node being deleted with the subtree rooted at it's only child.