×

# binary search tree deletion

 2 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 26●6●8●9 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;
}

2★rashedcs
49751755
accept rate: 4%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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