We have seen insertion in and displaying of Threaded binary tree (click here -> javascript:nicTemp(); )

Now lets see deletion of threaded binary tree;

For deletion we have to consider three cases:

CASE-1 : Node to be deleted is a leaf node.

CASE-2 : Node to be deleted has only one child.

CASE-3 : Node to be deleted has two children

Lets discuss each case in detail

Again we have two cases :

struct Node* Case_1(struct Node* root , struct Node* par ,struct Node* ptr )

{

// If Node to be deleted is root

if (par == NULL)

root = NULL;

// If Node to be deleted is left of its parent

else if (ptr == par->left) {

par->lthread = true;

par->left = ptr->left;

}

//If Node to be deleted is right of its parent

else {

par->rthread = true;

par->right = ptr->right;

}

// Free memory and return new root

free(ptr);

return root;

{

// If Node to be deleted is root

if (par == NULL)

root = NULL;

// If Node to be deleted is left of its parent

else if (ptr == par->left) {

par->lthread = true;

par->left = ptr->left;

}

//If Node to be deleted is right of its parent

else {

par->rthread = true;

par->right = ptr->right;

}

// Free memory and return new root

free(ptr);

return root;

}

If Node to be deleted has left subtree, then after deletion right thread of its predecessor should point to its successor.

If Node to be deleted has right subtree, then after deletion left thread of its successor should point to its prredecessor.

struct Node* Case_2( struct Node* root, struct Node* par, struct Node* ptr )

{

struct Node* child;

// Initialize child

//Node to be deleted has left child.

if (ptr->lthread == false)

child = ptr->left;

// Node to be deleted has right child.

else

child = ptr->right;

// Node to be deleted is root Node.

if (par == NULL)

root = child;

// Node is left child of its parent.

else if (ptr == par->left)

par->left = child;

//Node is right child of its parent

else

par->right = child;

// Find successor and predecessor

Node* s = inordersuccessor (ptr);

Node* p = inorderpedecessor (ptr);

// If ptr has left subtree.

if (ptr->lthread == false)

p->right = s;

// If ptr has right subtree.

else {

if (ptr->rthread == false)

s->left = p;

}

free(ptr);

return root;

};

{

struct Node* child;

// Initialize child

//Node to be deleted has left child.

if (ptr->lthread == false)

child = ptr->left;

// Node to be deleted has right child.

else

child = ptr->right;

// Node to be deleted is root Node.

if (par == NULL)

root = child;

// Node is left child of its parent.

else if (ptr == par->left)

par->left = child;

//Node is right child of its parent

else

par->right = child;

// Find successor and predecessor

Node* s = inordersuccessor (ptr);

Node* p = inorderpedecessor (ptr);

// If ptr has left subtree.

if (ptr->lthread == false)

p->right = s;

// If ptr has right subtree.

else {

if (ptr->rthread == false)

s->left = p;

}

free(ptr);

return root;

};

We find inorder successor of Node ptr (Node to be deleted) and then copy the information of this successor into Node ptr. After this inorder successor Node is deleted using either Case A or Case B.

{

// Find inorder successor and its parent.

struct Node* parsucc = ptr;

struct Node* succ = ptr->right;

// Find leftmost child of successor

while (succ->left != NULL) {

parsucc = succ;

succ = succ->left;

}

ptr->data = succ->data;

if (succ->lthread == true && succ->rthread == true)

root = Case_1(root, parsucc, succ);

else

root = Case_2(root, parsucc, succ);

return root;

}

Now , first we have to find the node in the tree and then different cases are applied to the node to be deleted

struct Node* delete_Node( struct Node *root, int key)

{

struct Node *parent= NULL;

struct Node *ptr= root;

//set true if key is found

bool found = false;

//search key in tree

while( ptr != NULL)

{

if(ptr -> data == key )

{

found = true;

break;

}

parent = ptr;

if ( key < ptr -> data)

{

if(ptr -> lthread == false)

ptr = ptr -> left;

else

break;

}

else

{

if( ptr -> rthread == false)

ptr = ptr -> right;

else

break;

}

}

if( found == false)

cout<<"Data is not present in the tree\n";

else{

if(ptr -> lthread == false && ptr -> rthread == false )

root= Case_3(root, parent, ptr);

else if(ptr -> lthread == true && ptr -> rthread == false )

root= Case_2(root, parent, ptr);

else if(ptr -> lthread == false && ptr -> rthread == true )

root= Case_2(root, parent, ptr);

else if(ptr -> lthread == true && ptr -> rthread == true )

root= Case_1(root, parent, ptr);

}

}

{

struct Node *parent= NULL;

struct Node *ptr= root;

//set true if key is found

bool found = false;

//search key in tree

while( ptr != NULL)

{

if(ptr -> data == key )

{

found = true;

break;

}

parent = ptr;

if ( key < ptr -> data)

{

if(ptr -> lthread == false)

ptr = ptr -> left;

else

break;

}

else

{

if( ptr -> rthread == false)

ptr = ptr -> right;

else

break;

}

}

if( found == false)

cout<<"Data is not present in the tree\n";

else{

if(ptr -> lthread == false && ptr -> rthread == false )

root= Case_3(root, parent, ptr);

else if(ptr -> lthread == true && ptr -> rthread == false )

root= Case_2(root, parent, ptr);

else if(ptr -> lthread == false && ptr -> rthread == true )

root= Case_2(root, parent, ptr);

else if(ptr -> lthread == true && ptr -> rthread == true )

root= Case_1(root, parent, ptr);

}

}

## Comments