You are not logged in. Please login at www.codechef.com to post your questions!

×

binary search tree deletion

can anyone give me pseudo code for deletion of two child node in binary search tree.please explain it also.any example will be great. reply soon thanks in advance

asked 13 Jul '13, 14:50

whiteknight321's gravatar image

0★whiteknight321
26689
accept rate: 0%


Procedure :
 1. At first locate the node to be deleted.

 2. If the node is a leaf node :
      i. If the node is left child of the parent , make null the left pointer of its parent node and free the space for the node.
     ii. If the node is right child of the parent , make null the right pointer of its parent node and free the space for the node.

 3. If the node has one child
     i. If the node to be deleted is a left chile of its parent , then make link between the left pointer of its parent node and the child node to be deleted. Then delete the node.
     ii.If the node to be deleted is a right child of its parent , then make link between the right pointer of its parent node and the child node to be deleted. Then delete the node.

 4. If the node to be deleted has two child :
     i. Locate the node with maximum value from the left sub-tree of  the node to be deleted.
     ii. Replace the node value to be deleted by the node found in step 4(i)

 5. Now we get updated output


C++ implementation :

node Delete(node root, int data)
{
if(root == NULL) return root;

else if(data < root->data) root->left = Delete(root->left,data);

else if (data > root->data) root->right = Delete(root->right,data);

else
{
///Case 1: No child
if(root->left == NULL && root->right == NULL)
{
delete root;
root = NULL;
}

///Case 2: One child
else if(root->left == NULL)
{
struct node temp = root;
root= root->right;
delete temp;
}

else if(root->right == NULL)
{
struct node
temp = root;
root = root->left;
delete temp;
}

///case 3: 2 children
else
{
node *temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right,temp->data);
}
}
return root;
}

link

answered 09 Nov '16, 08:54

rashedcs's gravatar image

2★rashedcs
49751755
accept rate: 4%

edited 09 Nov '16, 08:57

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,345
×1,911
×1,656

question asked: 13 Jul '13, 14:50

question was seen: 3,678 times

last updated: 09 Nov '16, 08:57