binary tree deletion of one child node

Question

I have a very simple question on BST deleting one child node case.

I want to check for the case where my root has one child but the child has in turn two child nodes. Should it still remove the entire tree ?

for eg I have

      5
     / 
    6  
   / \
  9  10

If I do delete(5). Should it remove the entire tree as the 5 has only one child ie 6 but 6 in turn has two child nodes. Should 6 also in turn have just one child or we dont care about how many child nodes 6 has when deleting the root 5 for one child condition

Answer 1

Deleting a node in Binary tree only involves three cases,

• Deleting Leaf node [node with no child]
• Deleting node with 1 child
• Deleting node with 2 children

Deleting leaf node, just free the node space and make the parent's child link to null.

Deleting node with 1 child remove the node and make the grandchildren as its child.

      10
     / \
    5   15
   /     \
  2      17  
 / \
1   3

here if we wish to delete 5, make 2 as child of 10, so the tree becomes

      10
     / \
    2   15
   / \    \
  1   3   17

This also applies for deleting 15 from tree.

http://webdocs.cs.ualberta.ca/~holte/T26/del-from-bst.html

Answer 2

I binary search tree (yours in not one) when a node has only one child, you can remove it and graft its child at its place (whatever the child's subtree is) while keeping the binary search tree property. Here is an example:

      7
     / \
    5   9
   /
  3
 / \
1   4

Then if I remove the 5 and replace it by its only subtree I get

    7
   / \
  3   9
 / \
1   4

Which is still a BST.