How to delete a node with 2 children nodes in a binary search tree?

Question

How to delete a node with 2 children nodes in a binary tree?

Is there any kind of method to remove it? I googled it. But didn't get clear idea about it. Anybody explain it with diagrammatic representation?

How to delete the node '5' from the this image and what might be the outcome?

Answer 1

you replace said node with the left most child on its right side, or the right most child on its left side. You then delete the child from the bottom that it was replaced with.

Deleting five could yield either a tree with 3 as its root or 18 as its root, depending on which direction you take.

It looks like you got that image from this site: http://www.algolist.net/Data_structures/Binary_search_tree/Removal

It shows the algorithm you want with images too.

Answer 2

For deleting a Node there are three scenarios possible..

1. Node is a leaf node: This is a simple case, figure out whether this node is left or right node of parent and set null as child for the parent for that side.
2. Node is having one child: Establish a direct link between parent node and child node of this node.
3. Node has two children: This is little tricky.. the steps involved in this are.
   1. First find the successor (or predecessor) of the this node.
   2. Delete the successor (or predecessor) from the tree.
   3. Replace the node to be deleted with the successor (or predecessor)

Before knowing the concept of deletion, we should understand the concept of successor and predecessors

Successor: In a binary tree successor of a node is the smallest node of the tree that is strictly greater then this node.

There are two possible cases with a node

• A node has right children: In this case the leftmost child of the right sub-tree will be successor.

• A node has no children: Go to the parent node and find a node for which this node is part of left sub-tree.

  public Node sucessor(Node node) {
  Node sucessor = null;
  if (node.getRightNode() != null) {
      Node newNode = node.getRightNode();
      while (newNode != null) {
          sucessor = newNode;
          newNode = newNode.getLeftNode();
      }
  } else {
      sucessor = findRightParent(node);
  }
  return sucessor;
  }
  private Node findRightParent(Node node) {
  Node newNode = null;
  if (node.getParentNode() != null) {
      if (node.getParentNode().getLeftNode() == node) {
          newNode = node.getParentNode();
      } else {
          newNode = findRightParent(node.getParentNode());
      }
  }
  return newNode;
  }
  

Now the deletion logic

     public void deleteNode(Node node) {
    // Node is a leaf node //
    if( node.getLeftNode() == null && node.getRightNode() == null){
        if(isRightNode(node.getParentNode(), node)){
            node.getParentNode().setRightNode(null);
        }else{
            node.getParentNode().setLeftNode(null);
        }
        // Only left child is there//
    }else if( node.getLeftNode() != null && node.getRightNode() == null){
        if(isRightNode(node.getParentNode(), node)){
            node.getParentNode().setRightNode(node.getLeftNode());
        }else{
            node.getParentNode().setLeftNode(node.getLeftNode());
        }
        // Only Right child is there //
    }else if( node.getLeftNode() == null && node.getRightNode() != null){
        if( isRightNode(node.getParentNode(), node)){
            node.getParentNode().setRightNode(node.getRightNode());
        }else{
            node.getParentNode().setLeftNode(node.getRightNode());
        }
        // Both Left and Right children are their//
    }else{
        Node psNode = predessor(node);
        deleteNode(psNode);
        psNode.setParentNode(node.getParentNode());
        psNode.setLeftNode(node.getLeftNode());
        psNode.setRightNode(node.getRightNode());
        if( isRightNode(node.getParentNode(), node)){
            node.getParentNode().setRightNode(psNode);
        }else{
            node.getParentNode().setLeftNode(psNode);
        }
    }

    }

Solution is taken from http://coder2design.com/binary-tree/

Also they have explained the flow of traversal and insertion with full source code.