Árbol de búsqueda binario enhebrado | Supresión

Un Node de árbol binario enhebrado se parece a lo siguiente.

struct Node {
    struct Node *left, *right;
    int info;
 
    // false if left pointer points to predecessor
    // in Inorder Traversal
    bool lthread;
 
    // false if right pointer points to predecessor
    // in Inorder Traversal
    bool rthread;
};

static class Node {
    Node left, right;
    int info;
 
    // True if left pointer points to predecessor
    // in Inorder Traversal
    boolean lthread;
 
    // True if right pointer points to predecessor
    // in Inorder Traversal
    boolean rthread;
};
 
 
// This code contributed by aashish1995

class Node:
    def __init__(self):
        self.info = 0;
        self.left = None;
        self.right = None;
         
        # True if left pointer points to predecessor
        # in Inorder Traversal
        self.lthread = False;;
     
        # True if right pointer points to predecessor
        # in Inorder Traversal
        self.rthread = False;
 
# This code contributed by umadevi9616

public
  class Node
  {
    public
      Node left,
    right;
    public
      int info;
 
    // True if left pointer points to predecessor
    // in Inorder Traversal
    public
      bool lthread;
 
    // True if right pointer points to predecessor
    // in Inorder Traversal
    public
      bool rthread;
  };
 
// This code is contributed by aashish1995

<script>
 class Node {
     constructor(){
  
     this.left = null, this.right = null;
     this.info = 0;
 
    // True if left pointer points to predecessor
    // in Inorder Traversal
    this.lthread = false;
 
    // True if right pointer points to predecessor
    // in Inorder Traversal
    this.rthread = false;
}
}
// This code contributed by aashish1995
</script>

Ya hemos discutido la inserción del árbol de búsqueda binario enhebrado 

En el borrado primero se busca la clave a borrar, y luego existen diferentes casos para borrar el Node en el que se encuentra la clave. 

// Deletes a key from threaded BST with given root and
// returns new root of BST.
struct Node* delThreadedBST(struct Node* root, int dkey)
{
    // Initialize parent as NULL and ptrent
    // Node as root.
    struct Node *par = NULL, *ptr = root;
 
    // Set true if key is found
    int found = 0;
 
    // Search key in BST : find Node and its
    // parent.
    while (ptr != NULL) {
        if (dkey == ptr->info) {
            found = 1;
            break;
        }
        par = ptr;
        if (dkey < ptr->info) {
            if (ptr->lthread == false)
                ptr = ptr->left;
            else
                break;
        }
        else {
            if (ptr->rthread == false)
                ptr = ptr->right;
            else
                break;
        }
    }
 
    if (found == 0)
        printf("dkey not present in tree\n");
 
    // Two Children
    else if (ptr->lthread == false && ptr->rthread == false)
        root = caseC(root, par, ptr);
 
    // Only Left Child
    else if (ptr->lthread == false)
        root = caseB(root, par, ptr);
 
    // Only Right Child
    else if (ptr->rthread == false)
        root = caseB(root, par, ptr);
 
    // No child
    else
        root = caseA(root, par, ptr);
 
    return root;
}

// Deletes a key from threaded BST with given root and
// returns new root of BST.
Node delThreadedBST(Node root, int dkey)
{
    // Initialize parent as null and ptrent
    // Node as root.
    Node par = null, ptr = root;
 
    // Set true if key is found
    int found = 0;
 
    // Search key in BST : find Node and its
    // parent.
    while (ptr != null) {
        if (dkey == ptr.info) {
            found = 1;
            break;
        }
        par = ptr;
        if (dkey < ptr.info) {
            if (ptr.lthread == false)
                ptr = ptr.left;
            else
                break;
        }
        else {
            if (ptr.rthread == false)
                ptr = ptr.right;
            else
                break;
        }
    }
 
    if (found == 0)
        System.out.printf("dkey not present in tree\n");
 
    // Two Children
    else if (ptr.lthread == false && ptr.rthread == false)
        root = caseC(root, par, ptr);
 
    // Only Left Child
    else if (ptr.lthread == false)
        root = caseB(root, par, ptr);
 
    // Only Right Child
    else if (ptr.rthread == false)
        root = caseB(root, par, ptr);
 
    // No child
    else
        root = caseA(root, par, ptr);
 
    return root;
}
 
// This code is contributed by gauravrajput1

# Deletes a key from threaded BST with given root and
# returns new root of BST.
def delThreadedBST(root, dkey):
 
    # Initialize parent as None and ptrent
    # Node as root.
    par = None;
    ptr = root;
 
    # Set True if key is found
    found = 0;
 
    # Search key in BST : find Node and its
    # parent.
    while (ptr != None):
        if (dkey == ptr.info):
            found = 1;
            break;
         
        par = ptr;
        if (dkey < ptr.info):
            if (ptr.lthread == False)
                ptr = ptr.left;
            else
                break;
         
        else:
            if (ptr.rthread == False)
                ptr = ptr.right;
            else
                break;
 
    if (found == 0):
        print("dkey not present in tree");
 
    # Two Children
    else if(ptr.lthread == False and ptr.rthread == False):
        root = caseC(root, par, ptr);
 
    # Only Left Child
    else if(ptr.lthread == False):
        root = caseB(root, par, ptr);
 
    # Only Right Child
    else if(ptr.rthread == False):
        root = caseB(root, par, ptr);
 
    # No child
    else:
        root = caseA(root, par, ptr);
 
    return root;
 
# This code is contributed by Rajput-Ji

// Deletes a key from threaded BST with given root and
// returns new root of BST.
Node delThreadedBST(Node root, int dkey)
{
    // Initialize parent as null and ptrent
    // Node as root.
    Node par = null, ptr = root;
 
    // Set true if key is found
    int found = 0;
 
    // Search key in BST : find Node and its
    // parent.
    while (ptr != null) {
        if (dkey == ptr.info) {
            found = 1;
            break;
        }
        par = ptr;
        if (dkey < ptr.info) {
            if (ptr.lthread == false)
                ptr = ptr.left;
            else
                break;
        }
        else {
            if (ptr.rthread == false)
                ptr = ptr.right;
            else
                break;
        }
    }
 
    if (found == 0)
        Console.Write("dkey not present in tree\n");
 
    // Two Children
    else if (ptr.lthread == false && ptr.rthread == false)
        root = caseC(root, par, ptr);
 
    // Only Left Child
    else if (ptr.lthread == false)
        root = caseB(root, par, ptr);
 
    // Only Right Child
    else if (ptr.rthread == false)
        root = caseB(root, par, ptr);
 
    // No child
    else
        root = caseA(root, par, ptr);
 
    return root;
}
 
// This code is contributed by gauravrajput1

<script>
// Deletes a key from threaded BST with given root and
// returns new root of BST.
function delThreadedBST(root , dkey)
{
    // Initialize parent as null and ptrent
    // Node as root.
    var par = null, ptr = root;
 
    // Set true if key is found
    var found = 0;
 
    // Search key in BST : find Node and its
    // parent.
    while (ptr != null) {
        if (dkey == ptr.info) {
            found = 1;
            break;
        }
        par = ptr;
        if (dkey < ptr.info) {
            if (ptr.lthread == false)
                ptr = ptr.left;
            else
                break;
        }
        else {
            if (ptr.rthread == false)
                ptr = ptr.right;
            else
                break;
        }
    }
 
    if (found == 0)
        document.write("dkey not present in tree\n");
 
    // Two Children
    else if (ptr.lthread == false && ptr.rthread == false)
        root = caseC(root, par, ptr);
 
    // Only Left Child
    else if (ptr.lthread == false)
        root = caseB(root, par, ptr);
 
    // Only Right Child
    else if (ptr.rthread == false)
        root = caseB(root, par, ptr);
 
    // No child
    else
        root = caseA(root, par, ptr);
 
    return root;
}
 
// This code is contributed by gauravrajput1
</script>

Caso A: es necesario eliminar el Node hoja 

En BST, para eliminar un Node de hoja, el puntero izquierdo o derecho del padre se estableció en NULL. Aquí, en lugar de establecer el puntero en NULL, se crea un hilo. 
Si el Node de hoja que se va a eliminar se deja hijo de su padre, luego de la eliminación, el puntero izquierdo del padre debe convertirse en un hilo que apunta a su predecesor del Node padre después de la eliminación. 

par -> lthread = true;
par -> left = ptr -> left;

Si el Node de hoja que se va a eliminar es el hijo derecho de su padre, luego de la eliminación, el puntero derecho del padre debe convertirse en un hilo que apunta a su sucesor. El Node que era el sucesor en orden del Node hoja antes de la eliminación se convertirá en el sucesor en orden del Node principal después de la eliminación. 
 

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* caseA(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;
    }
    else {
        par->rthread = true;
        par->right = ptr->right;
    }
 
    // Free memory and return new root
    free(ptr);
    return root;
}

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
Node caseA(Node root, Node par,
                   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;
    }
    else {
        par.rthread = true;
        par.right = ptr.right;
    }
 
    return root;
}
 
// This code is contributed by gauravrajput1

# Here 'par' is pointer to parent Node and 'ptr' is
# pointer to current Node.
def caseA(root,par,ptr):
   
  # If Node to be deleted is root
    if (par == None):
        root = None
         
     # If Node to be deleted is left
    # of its parent
    elif(ptr == par.left):
        par.lthread = true
        par.left = ptr.left
    else:
        par.rthread = true
        par.right = ptr.right
return root
 
# This code is contributed by Patel2127.

// Here 'par' is pointer to parent Node and
// 'ptr' is pointer to current Node.
Node caseA(Node root, Node par, 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;
    }
    else
    {
        par.rthread = true;
        par.right = ptr.right;
    }
    return root;
}
 
// This code is contributed by rutvik_56

<script>
 
// Here 'par' is pointer to parent Node and
// 'ptr' is pointer to current Node.
function caseA(root, par, 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;
    }
    else
    {
        par.rthread = true;
        par.right = ptr.right;
    }
    return root;
}
 
// This code is contributed by rag2127
 
</script>

Caso B: el Node a eliminar tiene solo un hijo 
Después de eliminar el Node como en un BST, se descubre el sucesor en orden y el predecesor en orden del Node. 

s = inSucc(ptr);
p = inPred(ptr);

Si el Node que se eliminará tiene un subárbol izquierdo, luego de la eliminación, el subproceso derecho de su predecesor debe apuntar a su sucesor. 

p->right = s;

Antes de la eliminación, el 15 es el predecesor y el 2 es el sucesor del 16. Después de la eliminación del 16, el Node 20 se convierte en el sucesor del 15, por lo que el subproceso derecho del 15 apuntará al 20. 
Si el Node que se eliminará tiene un subárbol derecho, entonces, después de la eliminación, el subproceso izquierdo de su sucesor debe apuntar a su predecesor. 

s->left = p;

Antes de la eliminación de 25 es el predecesor y 34 es el sucesor de 30. Después de la eliminación de 30, el Node 25 se convierte en el predecesor de 34, por lo que el subproceso izquierdo de 34 apuntará a 25. 

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* caseB(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;
    else
        par->right = child;
 
    // Find successor and predecessor
    Node* s = inSucc(ptr);
    Node* p = inPred(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;
}

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
static Node caseB(Node root, Node par,
                   Node ptr)
{
    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;
    else
        par.right = child;
 
    // Find successor and predecessor
    Node s = inSucc(ptr);
    Node p = inPred(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;
    }
    return root;
}
 
// This code is contributed by gauravrajput1

# Here 'par' is pointer to parent Node and 'ptr' is
# pointer to current Node.
def caseB(root, par, ptr):
    child = None;
 
    # 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 == None):
        root = child;
 
    # Node is left child of its parent.
    elif(ptr == par.left):
        par.left = child;
    else:
        par.right = child;
 
    # Find successor and predecessor
    s = inSucc(ptr);
    p = inPred(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;
     
    return root;
 
# This code is contributed by umadevi9616

// Here 'par' is pointer to parent Node and
// 'ptr' is pointer to current Node.
static Node caseB(Node root, Node par,
                  Node ptr)
{
    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;
    else
        par.right = child;
 
    // Find successor and predecessor
    Node s = inSucc(ptr);
    Node p = inPred(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;
    }
    return root;
}
 
// This code is contributed by gauravrajput1

<script>
 
// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
function caseB(root,par,ptr)
{
    let 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;
    else
        par.right = child;
  
    // Find successor and predecessor
    let s = inSucc(ptr);
    let p = inPred(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;
    }
    return root;
}
 
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Caso C: el Node a eliminar tiene dos hijos 

Encontramos el sucesor en orden del Node ptr (Node a eliminar) y luego copiamos la información de este sucesor en el Node ptr. Después de este Node sucesor en orden, se elimina utilizando el Caso A o el Caso B. 

// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* caseC(struct Node* root, struct Node* par,
                   struct Node* ptr)
{
    // 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->info = succ->info;
 
    if (succ->lthread == true && succ->rthread == true)
        root = caseA(root, parsucc, succ);
    else
        root = caseB(root, parsucc, succ);
 
    return root;
}

// Here 'par' is pointer to parent Node and 'ptr' is
    // pointer to current Node.
    static Node caseC(Node root, Node par,
                      Node ptr)
    {
       
        // Find inorder successor and its parent.
        Node parsucc = ptr;
        Node succ = ptr.right;
 
        // Find leftmost child of successor
        while (succ.lthread == false) {
            parsucc = succ;
            succ = succ.left;
        }
 
        ptr.info = succ.info;
 
        if (succ.lthread == true && succ.rthread == true)
            root = caseA(root, parsucc, succ);
        else
            root = caseB(root, parsucc, succ);
 
        return root;
    }
 
// This code is contributed by umadevi9616

// Here 'par' is pointer to parent Node and 'ptr' is
    // pointer to current Node.
    static Node caseC(Node root, Node par,
                      Node ptr)
    {
        // Find inorder successor and its parent.
        Node parsucc = ptr;
        Node succ = ptr.right;
 
        // Find leftmost child of successor
        while (succ.lthread == false) {
            parsucc = succ;
            succ = succ.left;
        }
 
        ptr.info = succ.info;
 
        if (succ.lthread == true && succ.rthread == true)
            root = caseA(root, parsucc, succ);
        else
            root = caseB(root, parsucc, succ);
 
        return root;
    }
 
// This code is contributed by umadevi9616

<script>
 // Here 'par' is pointer to parent Node and 'ptr' is
      // pointer to current Node.
      function caseC(root, par, ptr)
      {
       
        // Find inorder successor and its parent.
        var parsucc = ptr;
        var succ = ptr.right;
 
        // Find leftmost child of successor
        while (succ.lthread == false) {
          parsucc = succ;
          succ = succ.left;
        }
 
        ptr.info = succ.info;
 
        if (succ.lthread == true && succ.rthread == true)
          root = caseA(root, parsucc, succ);
        else root = caseB(root, parsucc, succ);
 
        return root;
      }
       
      // This code is contributed by gauravrajput1
</script>

# Here 'par' is pointer to parent Node and 'ptr' is
# pointer to current Node.
def caseC(root, par, ptr):
   
    # Find inorder successor and its parent.
    parsucc = ptr;
    succ = ptr.right;
 
    # Find leftmost child of successor
    while (succ.lthread == False):
        parsucc = succ;
        succ = succ.left;
     
 
    ptr.info = succ.info;
 
    if (succ.lthread == True and succ.rthread == True):
        root = caseA(root, parsucc, succ);
    else:
        root = caseB(root, parsucc, succ);
 
    return root;
 
 
# This code contributed by umadevi9616

A continuación se muestra el código completo: 

// Complete C++ program to demonstrate deletion
// in threaded BST
#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    struct Node *left, *right;
    int info;
 
    // false if left pointer points to predecessor
    // in Inorder Traversal
    bool lthread;
 
    // false if right pointer points to predecessor
    // in Inorder Traversal
    bool rthread;
};
 
// Insert a Node in Binary Threaded Tree
struct Node* insert(struct Node* root, int ikey)
{
    // Searching for a Node with given value
    Node* ptr = root;
    Node* par = NULL; // Parent of key to be inserted
    while (ptr != NULL) {
        // If key already exists, return
        if (ikey == (ptr->info)) {
            printf("Duplicate Key !\n");
            return root;
        }
 
        par = ptr; // Update parent pointer
 
        // Moving on left subtree.
        if (ikey < ptr->info) {
            if (ptr->lthread == false)
                ptr = ptr->left;
            else
                break;
        }
 
        // Moving on right subtree.
        else {
            if (ptr->rthread == false)
                ptr = ptr->right;
            else
                break;
        }
    }
 
    // Create a new Node
    Node* tmp = new Node;
    tmp->info = ikey;
    tmp->lthread = true;
    tmp->rthread = true;
 
    if (par == NULL) {
        root = tmp;
        tmp->left = NULL;
        tmp->right = NULL;
    }
    else if (ikey < (par->info)) {
        tmp->left = par->left;
        tmp->right = par;
        par->lthread = false;
        par->left = tmp;
    }
    else {
        tmp->left = par;
        tmp->right = par->right;
        par->rthread = false;
        par->right = tmp;
    }
 
    return root;
}
 
// Returns inorder successor using left
// and right children (Used in deletion)
struct Node* inSucc(struct Node* ptr)
{
    if (ptr->rthread == true)
        return ptr->right;
 
    ptr = ptr->right;
    while (ptr->lthread == false)
        ptr = ptr->left;
 
    return ptr;
}
 
// Returns inorder successor using rthread
// (Used in inorder)
struct Node* inorderSuccessor(struct Node* ptr)
{
    // If rthread is set, we can quickly find
    if (ptr->rthread == true)
        return ptr->right;
 
    // Else return leftmost child of right subtree
    ptr = ptr->right;
    while (ptr->lthread == false)
        ptr = ptr->left;
    return ptr;
}
 
// Printing the threaded tree
void inorder(struct Node* root)
{
    if (root == NULL)
        printf("Tree is empty");
 
    // Reach leftmost Node
    struct Node* ptr = root;
    while (ptr->lthread == false)
        ptr = ptr->left;
 
    // One by one print successors
    while (ptr != NULL) {
        printf("%d ", ptr->info);
        ptr = inorderSuccessor(ptr);
    }
}
 
struct Node* inPred(struct Node* ptr)
{
    if (ptr->lthread == true)
        return ptr->left;
 
    ptr = ptr->left;
    while (ptr->rthread == false)
        ptr = ptr->right;
    return ptr;
}
 
// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* caseA(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;
    }
    else {
        par->rthread = true;
        par->right = ptr->right;
    }
 
    // Free memory and return new root
    free(ptr);
    return root;
}
 
// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* caseB(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;
    else
        par->right = child;
 
    // Find successor and predecessor
    Node* s = inSucc(ptr);
    Node* p = inPred(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;
}
 
// Here 'par' is pointer to parent Node and 'ptr' is
// pointer to current Node.
struct Node* caseC(struct Node* root, struct Node* par,
                   struct Node* ptr)
{
    // Find inorder successor and its parent.
    struct Node* parsucc = ptr;
    struct Node* succ = ptr->right;
 
    // Find leftmost child of successor
    while (succ->lthread==false) {
        parsucc = succ;
        succ = succ->left;
    }
 
    ptr->info = succ->info;
 
    if (succ->lthread == true && succ->rthread == true)
        root = caseA(root, parsucc, succ);
    else
        root = caseB(root, parsucc, succ);
 
    return root;
}
 
// Deletes a key from threaded BST with given root and
// returns new root of BST.
struct Node* delThreadedBST(struct Node* root, int dkey)
{
    // Initialize parent as NULL and ptrent
    // Node as root.
    struct Node *par = NULL, *ptr = root;
 
    // Set true if key is found
    int found = 0;
 
    // Search key in BST : find Node and its
    // parent.
    while (ptr != NULL) {
        if (dkey == ptr->info) {
            found = 1;
            break;
        }
        par = ptr;
        if (dkey < ptr->info) {
            if (ptr->lthread == false)
                ptr = ptr->left;
            else
                break;
        }
        else {
            if (ptr->rthread == false)
                ptr = ptr->right;
            else
                break;
        }
    }
 
    if (found == 0)
        printf("dkey not present in tree\n");
 
    // Two Children
    else if (ptr->lthread == false && ptr->rthread == false)
        root = caseC(root, par, ptr);
 
    // Only Left Child
    else if (ptr->lthread == false)
        root = caseB(root, par, ptr);
 
    // Only Right Child
    else if (ptr->rthread == false)
        root = caseB(root, par, ptr);
 
    // No child
    else
        root = caseA(root, par, ptr);
 
    return root;
}
 
// Driver Program
int main()
{
    struct Node* root = NULL;
 
    root = insert(root, 20);
    root = insert(root, 10);
    root = insert(root, 30);
    root = insert(root, 5);
    root = insert(root, 16);
    root = insert(root, 14);
    root = insert(root, 17);
    root = insert(root, 13);
 
    root = delThreadedBST(root, 20);
    inorder(root);
 
    return 0;
}

// Complete Java program to demonstrate deletion
// in threaded BST
import java.util.*;
class solution {
 
    static class Node {
        Node left, right;
        int info;
 
        // True if left pointer points to predecessor
        // in Inorder Traversal
        boolean lthread;
 
        // True if right pointer points to predecessor
        // in Inorder Traversal
        boolean rthread;
    };
 
    // Insert a Node in Binary Threaded Tree
    static Node insert(Node root, int ikey)
    {
        // Searching for a Node with given value
        Node ptr = root;
        Node par = null; // Parent of key to be inserted
        while (ptr != null) {
            // If key already exists, return
            if (ikey == (ptr.info)) {
                System.out.printf("Duplicate Key !\n");
                return root;
            }
 
            par = ptr; // Update parent pointer
 
            // Moving on left subtree.
            if (ikey < ptr.info) {
                if (ptr.lthread == false)
                    ptr = ptr.left;
                else
                    break;
            }
 
            // Moving on right subtree.
            else {
                if (ptr.rthread == false)
                    ptr = ptr.right;
                else
                    break;
            }
        }
 
        // Create a new Node
        Node tmp = new Node();
        tmp.info = ikey;
        tmp.lthread = true;
        tmp.rthread = true;
 
        if (par == null) {
            root = tmp;
            tmp.left = null;
            tmp.right = null;
        }
        else if (ikey < (par.info)) {
            tmp.left = par.left;
            tmp.right = par;
            par.lthread = false;
            par.left = tmp;
        }
        else {
            tmp.left = par;
            tmp.right = par.right;
            par.rthread = false;
            par.right = tmp;
        }
 
        return root;
    }
 
    // Returns inorder successor using left
    // and right children (Used in deletion)
    static Node inSucc(Node ptr)
    {
        if (ptr.rthread == true)
            return ptr.right;
 
        ptr = ptr.right;
        while (ptr.lthread == false)
            ptr = ptr.left;
 
        return ptr;
    }
 
    // Returns inorder successor using rthread
    // (Used in inorder)
    static Node inorderSuccessor(Node ptr)
    {
        // If rthread is set, we can quickly find
        if (ptr.rthread == true)
            return ptr.right;
 
        // Else return leftmost child of right subtree
        ptr = ptr.right;
        while (ptr.lthread == false)
            ptr = ptr.left;
        return ptr;
    }
 
    // Printing the threaded tree
    static void inorder(Node root)
    {
        if (root == null)
            System.out.printf("Tree is empty");
 
        // Reach leftmost Node
        Node ptr = root;
        while (ptr.lthread == false)
            ptr = ptr.left;
 
        // One by one print successors
        while (ptr != null) {
            System.out.printf("%d ", ptr.info);
            ptr = inorderSuccessor(ptr);
        }
    }
 
    static Node inPred(Node ptr)
    {
        if (ptr.lthread == true)
            return ptr.left;
 
        ptr = ptr.left;
        while (ptr.rthread == false)
            ptr = ptr.right;
        return ptr;
      
    }
 
    // Here 'par' is pointer to parent Node and 'ptr' is
    // pointer to current Node.
    static Node caseA(Node root, Node par,
                      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;
        }
        else {
            par.rthread = true;
            par.right = ptr.right;
        }
 
        return root;
    }
 
    // Here 'par' is pointer to parent Node and 'ptr' is
    // pointer to current Node.
    static Node caseB(Node root, Node par,
                      Node ptr)
    {
        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;
        else
            par.right = child;
 
        // Find successor and predecessor
        Node s = inSucc(ptr);
        Node p = inPred(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;
        }
 
        return root;
    }
 
    // Here 'par' is pointer to parent Node and 'ptr' is
    // pointer to current Node.
    static Node caseC(Node root, Node par,
                      Node ptr)
    {
        // Find inorder successor and its parent.
        Node parsucc = ptr;
        Node succ = ptr.right;
 
        // Find leftmost child of successor
        while (succ.lthread == false) {
            parsucc = succ;
            succ = succ.left;
        }
 
        ptr.info = succ.info;
 
        if (succ.lthread == true && succ.rthread == true)
            root = caseA(root, parsucc, succ);
        else
            root = caseB(root, parsucc, succ);
 
        return root;
    }
 
    // Deletes a key from threaded BST with given root and
    // returns new root of BST.
    static Node delThreadedBST(Node root, int dkey)
    {
        // Initialize parent as null and ptrent
        // Node as root.
        Node par = null, ptr = root;
 
        // Set true if key is found
        int found = 0;
 
        // Search key in BST : find Node and its
        // parent.
        while (ptr != null) {
            if (dkey == ptr.info) {
                found = 1;
                break;
            }
            par = ptr;
            if (dkey < ptr.info) {
                if (ptr.lthread == false)
                    ptr = ptr.left;
                else
                    break;
            }
            else {
                if (ptr.rthread == false)
                    ptr = ptr.right;
                else
                    break;
            }
        }
 
        if (found == 0)
            System.out.printf("dkey not present in tree\n");
 
        // Two Children
        else if (ptr.lthread == false && ptr.rthread == false)
            root = caseC(root, par, ptr);
 
        // Only Left Child
        else if (ptr.lthread == false)
            root = caseB(root, par, ptr);
 
        // Only Right Child
        else if (ptr.rthread == false)
            root = caseB(root, par, ptr);
 
        // No child
        else
            root = caseA(root, par, ptr);
 
        return root;
    }
 
    // Driver Program
    public static void main(String args[])
    {
        Node root = null;
 
        root = insert(root, 20);
        root = insert(root, 10);
        root = insert(root, 30);
        root = insert(root, 5);
        root = insert(root, 16);
        root = insert(root, 14);
        root = insert(root, 17);
        root = insert(root, 13);
 
        root = delThreadedBST(root, 20);
        inorder(root);
    }
}
// This code is contributed by Arnab Kundu

# Complete Python program to demonstrate deletion
# in threaded BST
 
class Node:
    def __init__(self):
        self.info = 0;
        self.left = None;
        self.right = None;
         
        # True if left pointer points to predecessor
        # in Inorder Traversal
        self.lthread = False;
         
        # True if right pointer points to predecessor
        # in Inorder Traversal
        self.rthread = False;
 
# Insert a Node in Binary Threaded Tree
def insert(root, ikey):
   
    # Searching for a Node with given value
    ptr = root;
    par = None; # Parent of key to be inserted
    while (ptr != None):
       
        # If key already exists, return
        if (ikey == (ptr.info)):
            print("Duplicate Key !");
            return root;
         
 
        par = ptr; # Update parent pointer
 
        # Moving on left subtree.
        if (ikey < ptr.info):
            if (ptr.lthread == False):
                ptr = ptr.left;
            else:
                break;
         
        # Moving on right subtree.
        else:
            if (ptr.rthread == False):
                ptr = ptr.right;
            else:
                break;
         
    # Create a new Node
    tmp = Node();
    tmp.info = ikey;
    tmp.lthread = True;
    tmp.rthread = True;
 
    if (par == None):
        root = tmp;
        tmp.left = None;
        tmp.right = None;
    elif(ikey < (par.info)):
        tmp.left = par.left;
        tmp.right = par;
        par.lthread = False;
        par.left = tmp;
    else:
        tmp.left = par;
        tmp.right = par.right;
        par.rthread = False;
        par.right = tmp;
     
    return root;
 
# Returns inorder successor using left
# and right children (Used in deletion)
def inSucc(ptr):
    if (ptr.rthread == True):
        return ptr.right;
 
    ptr = ptr.right;
    while (ptr.lthread == False):
        ptr = ptr.left;
 
    return ptr;
 
# Returns inorder successor using rthread
# (Used in inorder)
def inorderSuccessor(ptr):
   
    # If rthread is set, we can quickly find
    if (ptr.rthread == True):
        return ptr.right;
 
    # Else return leftmost child of right subtree
    ptr = ptr.right;
    while (ptr.lthread == False):
        ptr = ptr.left;
    return ptr;
 
# Printing the threaded tree
def inorder(root):
    if (root == None):
        print("Tree is empty");
 
    # Reach leftmost Node
    ptr = root;
    while (ptr.lthread == False):
        ptr = ptr.left;
 
    # One by one print successors
    while (ptr != None):
        print( ptr.info, end=" ");
        ptr = inorderSuccessor(ptr);
     
def inPred(ptr):
    if (ptr.lthread == True):
        return ptr.left;
 
    ptr = ptr.left;
    while (ptr.rthread == False):
        ptr = ptr.right;
    return ptr;
 
# Here 'par' is pointer to parent Node and 'ptr' is
# pointer to current Node.
def caseA(root, par, ptr):
   
    # If Node to be deleted is root
    if (par == None):
        root = None;
 
    # If Node to be deleted is left
    # of its parent
    elif(ptr == par.left):
        par.lthread = True;
        par.left = ptr.left;
    else:
        par.rthread = True;
        par.right = ptr.right;
     
    return root;
 
# Here 'par' is pointer to parent Node and 'ptr' is
# pointer to current Node.
def caseB(root, par, ptr):
    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 == None):
        root = child;
 
    # Node is left child of its parent.
    elif(ptr == par.left):
        par.left = child;
    else:
        par.right = child;
 
    # Find successor and predecessor
    s = inSucc(ptr);
    p = inPred(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;
    return root;
 
# Here 'par' is pointer to parent Node and 'ptr' is
# pointer to current Node.
def caseC(root, par, ptr):
   
    # Find inorder successor and its parent.
    parsucc = ptr;
    succ = ptr.right;
 
    # Find leftmost child of successor
    while (succ.lthread == False):
        parsucc = succ;
        succ = succ.left;
     
    ptr.info = succ.info;
 
    if (succ.lthread == True and succ.rthread == True):
        root = caseA(root, parsucc, succ);
    else:
        root = caseB(root, parsucc, succ);
 
    return root;
 
# Deletes a key from threaded BST with given root and
# returns new root of BST.
def delThreadedBST(root, dkey):
   
    # Initialize parent as None and ptrent
    # Node as root.
    par = None;
    ptr = root;
 
    # Set True if key is found
    found = 0;
 
    # Search key in BST : find Node and its
    # parent.
    while (ptr != None):
        if (dkey == ptr.info):
            found = 1;
            break;
         
        par = ptr;
        if (dkey < ptr.info):
            if (ptr.lthread == False):
                ptr = ptr.left;
            else:
                break;
        else:
            if (ptr.rthread == False):
                ptr = ptr.right;
            else:
                break;
         
    if (found == 0):
        print("dkey not present in tree");
 
    # Two Children
    elif(ptr.lthread == False and ptr.rthread == False):
        root = caseC(root, par, ptr);
 
    # Only Left Child
    elif(ptr.lthread == False):
        root = caseB(root, par, ptr);
 
    # Only Right Child
    elif(ptr.rthread == False):
        root = caseB(root, par, ptr);
 
    # No child
    else:
        root = caseA(root, par, ptr);
 
    return root;
 
# Driver Program
if __name__ == '__main__':
    root = None;
 
    root = insert(root, 20);
    root = insert(root, 10);
    root = insert(root, 30);
    root = insert(root, 5);
    root = insert(root, 16);
    root = insert(root, 14);
    root = insert(root, 17);
    root = insert(root, 13);
 
    root = delThreadedBST(root, 20);
    inorder(root);
 
# This code is contributed by Rajput-Ji

// Complete C# program to demonstrate deletion
// in threaded BST
using System;
 
class GFG {
 
    public class Node {
        public Node left, right;
        public int info;
 
        // True if left pointer points to predecessor
        // in Inorder Traversal
        public bool lthread;
 
        // True if right pointer points to predecessor
        // in Inorder Traversal
        public bool rthread;
    };
 
    // Insert a Node in Binary Threaded Tree
    static Node insert(Node root, int ikey)
    {
        // Searching for a Node with given value
        Node ptr = root;
        Node par = null; // Parent of key to be inserted
        while (ptr != null) {
            // If key already exists, return
            if (ikey == (ptr.info)) {
                Console.Write("Duplicate Key !\n");
                return root;
            }
 
            par = ptr; // Update parent pointer
 
            // Moving on left subtree.
            if (ikey < ptr.info) {
                if (ptr.lthread == false)
                    ptr = ptr.left;
                else
                    break;
            }
 
            // Moving on right subtree.
            else {
                if (ptr.rthread == false)
                    ptr = ptr.right;
                else
                    break;
            }
        }
 
        // Create a new Node
        Node tmp = new Node();
        tmp.info = ikey;
        tmp.lthread = true;
        tmp.rthread = true;
 
        if (par == null) {
            root = tmp;
            tmp.left = null;
            tmp.right = null;
        }
        else if (ikey < (par.info)) {
            tmp.left = par.left;
            tmp.right = par;
            par.lthread = false;
            par.left = tmp;
        }
        else {
            tmp.left = par;
            tmp.right = par.right;
            par.rthread = false;
            par.right = tmp;
        }
 
        return root;
    }
 
    // Returns inorder successor using left
    // and right children (Used in deletion)
    static Node inSucc(Node ptr)
    {
        if (ptr.rthread == true)
            return ptr.right;
 
        ptr = ptr.right;
        while (ptr.lthread == false)
            ptr = ptr.left;
 
        return ptr;
    }
 
    // Returns inorder successor using rthread
    // (Used in inorder)
    static Node inorderSuccessor(Node ptr)
    {
        // If rthread is set, we can quickly find
        if (ptr.rthread == true)
            return ptr.right;
 
        // Else return leftmost child of right subtree
        ptr = ptr.right;
        while (ptr.lthread == false)
            ptr = ptr.left;
        return ptr;
    }
 
    // Printing the threaded tree
    static void inorder(Node root)
    {
        if (root == null)
            Console.Write("Tree is empty");
 
        // Reach leftmost Node
        Node ptr = root;
        while (ptr.lthread == false)
            ptr = ptr.left;
 
        // One by one print successors
        while (ptr != null) {
            Console.Write("{0} ", ptr.info);
            ptr = inorderSuccessor(ptr);
        }
    }
 
    static Node inPred(Node ptr)
    {
        if (ptr.lthread == true)
            return ptr.left;
 
        ptr = ptr.left;
        while (ptr.rthread == false)
            ptr = ptr.right;
        return ptr;
    }
 
    // Here 'par' is pointer to parent Node and 'ptr' is
    // pointer to current Node.
    static Node caseA(Node root, Node par,
                      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;
        }
        else {
            par.rthread = true;
            par.right = ptr.right;
        }
 
        return root;
    }
 
    // Here 'par' is pointer to parent Node and 'ptr' is
    // pointer to current Node.
    static Node caseB(Node root, Node par,
                      Node ptr)
    {
        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;
        else
            par.right = child;
 
        // Find successor and predecessor
        Node s = inSucc(ptr);
        Node p = inPred(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;
        }
 
        return root;
    }
 
    // Here 'par' is pointer to parent Node and 'ptr' is
    // pointer to current Node.
    static Node caseC(Node root, Node par,
                      Node ptr)
    {
        // Find inorder successor and its parent.
        Node parsucc = ptr;
        Node succ = ptr.right;
 
        // Find leftmost child of successor
        while (succ.lthread == false) {
            parsucc = succ;
            succ = succ.left;
        }
 
        ptr.info = succ.info;
 
        if (succ.lthread == true && succ.rthread == true)
            root = caseA(root, parsucc, succ);
        else
            root = caseB(root, parsucc, succ);
 
        return root;
    }
 
    // Deletes a key from threaded BST with given root and
    // returns new root of BST.
    static Node delThreadedBST(Node root, int dkey)
    {
        // Initialize parent as null and ptrent
        // Node as root.
        Node par = null, ptr = root;
 
        // Set true if key is found
        int found = 0;
 
        // Search key in BST : find Node and its
        // parent.
        while (ptr != null) {
            if (dkey == ptr.info) {
                found = 1;
                break;
            }
            par = ptr;
            if (dkey < ptr.info) {
                if (ptr.lthread == false)
                    ptr = ptr.left;
                else
                    break;
            }
            else {
                if (ptr.rthread == false)
                    ptr = ptr.right;
                else
                    break;
            }
        }
 
        if (found == 0)
            Console.Write("dkey not present in tree\n");
 
        // Two Children
        else if (ptr.lthread == false && ptr.rthread == false)
            root = caseC(root, par, ptr);
 
        // Only Left Child
        else if (ptr.lthread == false)
            root = caseB(root, par, ptr);
 
        // Only Right Child
        else if (ptr.rthread == false)
            root = caseB(root, par, ptr);
 
        // No child
        else
            root = caseA(root, par, ptr);
 
        return root;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        Node root = null;
 
        root = insert(root, 20);
        root = insert(root, 10);
        root = insert(root, 30);
        root = insert(root, 5);
        root = insert(root, 16);
        root = insert(root, 14);
        root = insert(root, 17);
        root = insert(root, 13);
 
        root = delThreadedBST(root, 20);
        inorder(root);
    }
}
 
// This code has been contributed by 29AjayKumar

<script>
 
      // Complete JavaScript program to demonstrate deletion
      // in threaded BST
      class Node {
        constructor() {
          this.info = 0;
          // True if left pointer points to predecessor
          // in Inorder Traversal
          this.lthread = false;
          // True if right pointer points to predecessor
          // in Inorder Traversal
          this.rthread = false;
          this.left = null;
          this.right = null;
        }
      }
 
      // Insert a Node in Binary Threaded Tree
      function insert(root, ikey) {
        // Searching for a Node with given value
        var ptr = root;
        var par = null; // Parent of key to be inserted
        while (ptr != null) {
          // If key already exists, return
          if (ikey == ptr.info) {
            document.write("Duplicate Key !<br>");
            return root;
          }
 
          par = ptr; // Update parent pointer
 
          // Moving on left subtree.
          if (ikey < ptr.info) {
            if (ptr.lthread == false) ptr = ptr.left;
            else break;
          }
 
          // Moving on right subtree.
          else {
            if (ptr.rthread == false) ptr = ptr.right;
            else break;
          }
        }
 
        // Create a new Node
        var tmp = new Node();
        tmp.info = ikey;
        tmp.lthread = true;
        tmp.rthread = true;
 
        if (par == null) {
          root = tmp;
          tmp.left = null;
          tmp.right = null;
        } else if (ikey < par.info) {
          tmp.left = par.left;
          tmp.right = par;
          par.lthread = false;
          par.left = tmp;
        } else {
          tmp.left = par;
          tmp.right = par.right;
          par.rthread = false;
          par.right = tmp;
        }
 
        return root;
      }
 
      // Returns inorder successor using left
      // and right children (Used in deletion)
      function inSucc(ptr) {
        if (ptr.rthread == true) return ptr.right;
 
        ptr = ptr.right;
        while (ptr.lthread == false) ptr = ptr.left;
 
        return ptr;
      }
 
      // Returns inorder successor using rthread
      // (Used in inorder)
      function inorderSuccessor(ptr) {
        // If rthread is set, we can quickly find
        if (ptr.rthread == true) return ptr.right;
 
        // Else return leftmost child of right subtree
        ptr = ptr.right;
        while (ptr.lthread == false) ptr = ptr.left;
        return ptr;
      }
 
      // Printing the threaded tree
      function inorder(root) {
        if (root == null) document.write("Tree is empty");
 
        // Reach leftmost Node
        var ptr = root;
        while (ptr.lthread == false) ptr = ptr.left;
 
        // One by one print successors
        while (ptr != null) {
          document.write(ptr.info + " ");
          ptr = inorderSuccessor(ptr);
        }
      }
 
      function inPred(ptr) {
        if (ptr.lthread == true) return ptr.left;
 
        ptr = ptr.left;
        while (ptr.rthread == false) ptr = ptr.right;
        return ptr;
      }
 
      // Here 'par' is pointer to parent Node and 'ptr' is
      // pointer to current Node.
      function caseA(root, par, 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;
        } else {
          par.rthread = true;
          par.right = ptr.right;
        }
 
        return root;
      }
 
      // Here 'par' is pointer to parent Node and 'ptr' is
      // pointer to current Node.
      function caseB(root, par, ptr) {
        var 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;
        else par.right = child;
 
        // Find successor and predecessor
        var s = inSucc(ptr);
        var p = inPred(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;
        }
 
        return root;
      }
 
      // Here 'par' is pointer to parent Node and 'ptr' is
      // pointer to current Node.
      function caseC(root, par, ptr) {
        // Find inorder successor and its parent.
        var parsucc = ptr;
        var succ = ptr.right;
 
        // Find leftmost child of successor
        while (succ.lthread == false) {
          parsucc = succ;
          succ = succ.left;
        }
 
        ptr.info = succ.info;
 
        if (succ.lthread == true && succ.rthread == true)
          root = caseA(root, parsucc, succ);
        else root = caseB(root, parsucc, succ);
 
        return root;
      }
 
      // Deletes a key from threaded BST with given root and
      // returns new root of BST.
      function delThreadedBST(root, dkey) {
        // Initialize parent as null and ptrent
        // Node as root.
        var par = null,
          ptr = root;
 
        // Set true if key is found
        var found = 0;
 
        // Search key in BST : find Node and its
        // parent.
        while (ptr != null) {
          if (dkey == ptr.info) {
            found = 1;
            break;
          }
          par = ptr;
          if (dkey < ptr.info) {
            if (ptr.lthread == false)
            ptr = ptr.left;
            else break;
          } else {
            if (ptr.rthread == false)
            ptr = ptr.right;
            else break;
          }
        }
 
        if (found == 0)
        document.write("dkey not present in tree<br>");
        // Two Children
        else if (ptr.lthread == false && ptr.rthread == false)
          root = caseC(root, par, ptr);
        // Only Left Child
        else if (ptr.lthread == false)
        root = caseB(root, par, ptr);
        // Only Right Child
        else if (ptr.rthread == false)
        root = caseB(root, par, ptr);
        // No child
        else root = caseA(root, par, ptr);
 
        return root;
      }
 
      // Driver code
      var root = null;
 
      root = insert(root, 20);
      root = insert(root, 10);
      root = insert(root, 30);
      root = insert(root, 5);
      root = insert(root, 16);
      root = insert(root, 14);
      root = insert(root, 17);
      root = insert(root, 13);
 
      root = delThreadedBST(root, 20);
      inorder(root);
       
</script>

5 10 13 14 16 17 30 

Este artículo es una contribución de Anuj Chauhan . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.