Friday, February 3, 2012

Remove Duplicate nodes in BST/BT

Write A Program to Remove Duplicates from BST.

Strategy:
Assuming if duplicate is there in inserting in a BST we put that in the left.
So 2 cases are there :
1.duplicate is the left child of its replica.
2.duplicate is at the successor position of the node.

Pseudo Code:

func(Node *node)
  {
    if(!node)
    return;

if(isduplicateexist(node))
   {
    dupparent=find_dup_parent(node);
    if(dupparent ! =node)
      {
       dup=dupparent->right;
      dupparent->right=dupparent->right->left;
      }
  else
   {
    dup=node->left;
    node->left=node->left->left;
   }

del (dup);
}
func(node->left);
func(node->right);
}

Remove Duplicates from BT.
http://www.mycareerstack.com/question/155/

1 comment:

  1. http://effprog.blogspot.in/2011/02/duplicate-removal-in-binary-search-tree.html
    http://shashank7s.blogspot.in/2011/03/write-program-to-remove-duplicates-from.html

    ReplyDelete