Skip to main content

Delete a node in binary tree

In a binary tree, a node represents a data element and contains references (or pointers) to its left and right child nodes, which may or may not exist. Deleting a node in a binary tree means removing the node from the tree structure and updating its parent and child nodes accordingly.

Delete binary tree node

When deleting a node in a binary tree, there are three possible scenarios to consider:

  1. Node is a leaf node: If the node to be deleted is a leaf node (i.e., it has no children), then simply remove the node from the tree.

  2. Node has one child: If the node to be deleted has only one child, then replace the node with its child node.

  3. Node has two children: If the node to be deleted has two children, then find the node with the next largest value in the tree (i.e., the node with the smallest value in the right subtree or the largest value in the left subtree), swap the values of the two nodes, and then delete the node with the larger value.

After deleting a node from a binary tree, the tree structure should be adjusted to maintain its integrity and ensure that it remains a valid binary tree. This may involve updating pointers of the parent and child nodes, balancing the tree, or restructuring the tree as necessary.

Code Example

/*
  C Program 
+ Delete a node in binary tree
*/
#include<stdio.h>

#include<stdlib.h>
 //structure of Binary Tree node
struct Node {
  int data;
  struct Node *left, *right;
};
//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes

struct Node *insert(int data) {
  //create dynamic memory to new binary tree node
  struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
  if (new_node != NULL) {
    //set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL; //Initially node right-pointer is NULL
  } else {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  //return reference
  return new_node;

}

//Find deleted node
void find(struct Node *root, struct Node *parent, int element, struct Node **result) {

  if (root != NULL && *result == NULL) {
    if (element == root->data) {
      *result = parent;
      return;
    }
    find(root->left, root, element, result);
    find(root->right, root, element, result);
  }

}
struct Node *getNode(struct Node *root) {
  //Replace root with any node
  //Either delete last node of tree
  //Or delete any node which are zero or have one child node
  struct Node *auxiliary = root, *temp = NULL;

  while (auxiliary->left != NULL) {
    temp = auxiliary;
    auxiliary = auxiliary->left;
  }

  temp->left = auxiliary->right;
  auxiliary->right = NULL;

  //change data
  (root)->data = auxiliary->data;

  return auxiliary;
}
void deleteNode(struct Node **root, int element) {

  if ( *root == NULL) return;

  struct Node *auxiliary = NULL, *head = NULL;

  if (( *root)->data == element) {
    //Delete root

    auxiliary = ( *root);

    if (( *root)->left == NULL) {
      //When no left sub tree
      ( *root) = ( *root)->right;
    } else if (( *root)->right == NULL) {
      //When no right sub tree
      ( *root) = ( *root)->left;
    } else {
      auxiliary = getNode( *root);
    }
  } else {
    //Find parent of deleted node
    find( *root, *root, element, & head);

    if (head != NULL) {
      //When deleted node are exist

      if (head->left != NULL && head->left->data == element) {
        auxiliary = head->left;

        if (auxiliary->left == NULL) {
          head->left = auxiliary->right;
        } else if (auxiliary->right == NULL) {
          head->left = auxiliary->left;
        } else {
          auxiliary = getNode(auxiliary);
        }

      } else if (head->right != NULL && head->right->data == element) {
        auxiliary = head->right;

        if (auxiliary->left == NULL) {
          head->right = auxiliary->right;
        } else if (auxiliary->right == NULL) {
          head->right = auxiliary->left;
        } else {
          auxiliary = getNode(auxiliary);
        }
      }

    }
  }

  if (auxiliary != NULL) {
    printf("\n Delete : %d ", element);
    free(auxiliary);
    auxiliary = NULL;
  } else {
    printf("\n Delete node %d is not found", element);
  }
  printf("\n");
}

//Display tree element inorder form
void inorder(struct Node *node) {

  if (node != NULL) {

    inorder(node->left);
    //Print node value
    printf("  %d", node->data);
    inorder(node->right);
  }
}
int main() {

  struct Node *root = NULL;
  /* Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      6    5    4
       \       /
        8     7 
  */
  //Insertion of binary tree nodes
  root = insert(1);
  root->left = insert(2);
  root->right = insert(3);
  root->right->right = insert(4);
  root->right->right->left = insert(7);
  root->right->left = insert(5);
  root->left->left = insert(6);
  root->left->left->right = insert(8);
  //Display Tree elements
  inorder(root);

  //Test case
  deleteNode( & root, 6);
  inorder(root);

  deleteNode( & root, 1);
  inorder(root);

  deleteNode( & root, 4);
  inorder(root);


  deleteNode( & root, 3);
  inorder(root);


  deleteNode( & root, 3);
  inorder(root);
  return 0;
}

Output

  6  8  2  1  5  3  7  4
 Delete : 6 
  8  2  1  5  3  7  4
 Delete : 1 
  2  8  5  3  7  4
 Delete : 4 
  2  8  5  3  7
 Delete : 3 
  2  8  5  7
 Delete node 3 is not found
  2  8  5  7
/*
C++ Program 
Delete a node in binary tree
*/

#include<iostream>

using namespace std;
class Node {
  public:
  int data;
  Node *left, *right;
  Node(int value) {
    this->data = value;
    this->left = this->right = NULL;
  }
};
class BinaryTree {
public:
  Node *root;
  Node *parent;
  BinaryTree() {
    this->root = NULL;
    this->parent = NULL;
  }
  void find_parent(Node *head, Node *result, int element) {
    if (head != NULL && this->parent == NULL) {
      if (element == head->data) {
        this->parent = result;
        return;
      }
      this->find_parent(head->left, head, element);
      this->find_parent(head->right, head, element);
    }
  }
  Node *getNode(Node *head) {
    Node *auxiliary = head, *temp = NULL;
    while (auxiliary->left != NULL) {
      temp = auxiliary;
      auxiliary = auxiliary->left;
    }
    temp->left = auxiliary->right;
    auxiliary->right = NULL;
    head->data = auxiliary->data;
    return auxiliary;
  }
  void deleteNode(int element) {
    Node *head = this->root;
    if (head == NULL) {
      return;
    }
    Node *auxiliary = NULL;
    if (head->data == element) {
      auxiliary = head;
      if (head->left == NULL) {
        this->root = head->right;
      } else
      if (head->right == NULL) {
        this->root = head->left;
      } else {
        auxiliary = this->getNode(head);
      }
    } else {
      this->parent = NULL;
      this->find_parent(head, head, element);
      if (this->parent != NULL) {
        if (this->parent->left != NULL && this->parent->left->data == element) {
          auxiliary = this->parent->left;
          if (auxiliary->left == NULL) {
            this->parent->left = auxiliary->right;
          } else
          if (auxiliary->right == NULL) {
            this->parent->left = auxiliary->left;
          } else {
            auxiliary = this->getNode(auxiliary);
          }
        } else
        if (this->parent->right != NULL && this->parent->right->data == element) {
          auxiliary = this->parent->right;
          if (auxiliary->left == NULL) {
            this->parent->right = auxiliary->right;
          } else
          if (auxiliary->right == NULL) {
            this->parent->right = auxiliary->left;
          } else {
            auxiliary = this->getNode(auxiliary);
          }
        }
      }
    }
    if (auxiliary != NULL) {
      cout << "\n Delete :  "<< element;
      auxiliary = NULL;
    } else {
      cout << "\n Delete node "<< element <<" is not found";
    }
    cout <<"\n";
  }
  void inorder(Node *head) {
    if (head != NULL) {
      this->inorder(head->left);
      cout << "  " << head->data;
      this->inorder(head->right);
    }
  }
};

int main() {
  BinaryTree obj;
  /* Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      6    5    4
       \       /
        8     7 
  */
  obj.root = new Node(1);
  obj.root->left = new Node(2);
  obj.root->right = new Node(3);
  obj.root->right->right = new Node(4);
  obj.root->right->right->left = new Node(7);
  obj.root->right->left = new Node(5);
  obj.root->left->left = new Node(6);
  obj.root->left->left->right = new Node(8);
  obj.inorder(obj.root);
  obj.deleteNode(6);
  obj.inorder(obj.root);
  obj.deleteNode(1);
  obj.inorder(obj.root);
  obj.deleteNode(4);
  obj.inorder(obj.root);
  obj.deleteNode(3);
  obj.inorder(obj.root);
  obj.deleteNode(3);
  obj.inorder(obj.root);
  return 0;
}

Output

  6  8  2  1  5  3  7  4
 Delete : 6 
  8  2  1  5  3  7  4
 Delete : 1 
  2  8  5  3  7  4
 Delete : 4 
  2  8  5  3  7
 Delete : 3 
  2  8  5  7
 Delete node 3 is not found
  2  8  5  7
/*
Java Program 
Delete a node in binary tree
*/

//Class of Binary Tree node
class Node {

  public int data;
  public Node left, right;
  //Make a tree node
  public Node(int value) {
    //Assign field values
    data = value;
    left = right = null;
  }
}


public class BinaryTree {

  public Node root;
  public Node parent;

  public BinaryTree() {
    //Set initial initial values
    root = null;
    parent = null;

  }
  //Find deleted node
  public void find_parent(Node head, Node result, int element) {

    if (head != null && this.parent == null) {
      if (element == head.data) {
        this.parent = result;
        return;
      }
      find_parent(head.left, head, element);
      find_parent(head.right, head, element);
    }

  }
  public Node getNode(Node head) {
    //Replace head with any node
    //Either delete last node of tree
    //Or delete any node which are zero or have one child node
    Node auxiliary = head, temp = null;

    while (auxiliary.left != null) {
      temp = auxiliary;
      auxiliary = auxiliary.left;
    }

    temp.left = auxiliary.right;
    auxiliary.right = null;

    //change data
    head.data = auxiliary.data;

    return auxiliary;
  }
  public void deleteNode(int element) {

    Node head = this.root;
    if (head == null) {
      return;
    }

    Node auxiliary = null;

    if (head.data == element) {
      //Delete head

      auxiliary = head;

      if (head.left == null) {
        //When no left sub tree
        this.root = head.right;

      } else if (head.right == null) {
        //When no right sub tree
        this.root = head.left;
      } else {
        auxiliary = getNode(head);
      }
    } else {

      this.parent = null;
      //Find parent of deleted node
      find_parent(head, head, element);

      if (this.parent != null) {
        //When deleted node are exist

        if (this.parent.left != null && this.parent.left.data == element) {
          auxiliary = this.parent.left;

          if (auxiliary.left == null) {
            this.parent.left = auxiliary.right;
          } else if (auxiliary.right == null) {
            this.parent.left = auxiliary.left;
          } else {
            auxiliary = getNode(auxiliary);
          }

        } else if (this.parent.right != null && this.parent.right.data == element) {
          auxiliary = this.parent.right;

          if (auxiliary.left == null) {
            this.parent.right = auxiliary.right;
          } else if (auxiliary.right == null) {
            this.parent.right = auxiliary.left;
          } else {
            auxiliary = getNode(auxiliary);
          }
        }

      }
    }

    if (auxiliary != null) {
      System.out.print("\n Delete :  " + element);

      auxiliary = null;
    } else {
      System.out.print("\n Delete node " + element + " is not found");
    }
    System.out.print("\n");
  }

  //Display tree element inorder form
  public void inorder(Node head) {

    if (head != null) {

      inorder(head.left);
      //Print node value
      System.out.print("  " + head.data);
      inorder(head.right);
    }
  }




  public static void main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();

    /* Make A Binary Tree
      -----------------------
              1
             /  \
            2    3
           /    /  \
          6    5    4
           \       /
            8     7 
      */
    //Binary tree nodes
    obj.root = new Node(1);
    obj.root.left = new Node(2);
    obj.root.right = new Node(3);
    obj.root.right.right = new Node(4);
    obj.root.right.right.left = new Node(7);
    obj.root.right.left = new Node(5);
    obj.root.left.left = new Node(6);
    obj.root.left.left.right = new Node(8);
    //Display Tree elements
    obj.inorder(obj.root);

    //Test case
    obj.deleteNode(6);
    obj.inorder(obj.root);

    obj.deleteNode(1);
    obj.inorder(obj.root);

    obj.deleteNode(4);
    obj.inorder(obj.root);


    obj.deleteNode(3);
    obj.inorder(obj.root);


    obj.deleteNode(3);
    obj.inorder(obj.root);
  }
}

Output

  6  8  2  1  5  3  7  4
 Delete : 6 
  8  2  1  5  3  7  4
 Delete : 1 
  2  8  5  3  7  4
 Delete : 4 
  2  8  5  3  7
 Delete : 3 
  2  8  5  7
 Delete node 3 is not found
  2  8  5  7
/*
C# Program 
Delete a node in binary tree
*/
using System;
//Class of Binary Tree node
public class Node {

  public int data;
  public Node left, right;
  //Make a tree node
  public Node(int value) {
    //Assign field values
    data = value;
    left = right = null;
  }
}


public class BinaryTree {

  public Node root;
  public Node parent;

  public BinaryTree() {
    //Set initial initial values
    root = null;
    parent = null;

  }
  //Find deleted node
  public void find_parent(Node head, Node result, int element) {

    if (head != null && this.parent == null) {
      if (element == head.data) {
        this.parent = result;
        return;
      }
      find_parent(head.left, head, element);
      find_parent(head.right, head, element);
    }

  }
  public Node getNode(Node head) {
    //Replace head with any node
    //Either delete last node of tree
    //Or delete any node which are zero or have one child node
    Node auxiliary = head, temp = null;

    while (auxiliary.left != null) {
      temp = auxiliary;
      auxiliary = auxiliary.left;
    }

    temp.left = auxiliary.right;
    auxiliary.right = null;

    //change data
    head.data = auxiliary.data;

    return auxiliary;
  }
  public void deleteNode(int element) {

    Node head = this.root;
    if (head == null) {
      return;
    }

    Node auxiliary = null;

    if (head.data == element) {
      //Delete head

      auxiliary = head;

      if (head.left == null) {
        //When no left sub tree
        this.root = head.right;

      } else if (head.right == null) {
        //When no right sub tree
        this.root = head.left;
      } else {
        auxiliary = getNode(head);
      }
    } else {

      this.parent = null;
      //Find parent of deleted node
      find_parent(head, head, element);

      if (this.parent != null) {
        //When deleted node are exist

        if (this.parent.left != null && this.parent.left.data == element) {
          auxiliary = this.parent.left;

          if (auxiliary.left == null) {
            this.parent.left = auxiliary.right;
          } else if (auxiliary.right == null) {
            this.parent.left = auxiliary.left;
          } else {
            auxiliary = getNode(auxiliary);
          }

        } else if (this.parent.right != null && this.parent.right.data == element) {
          auxiliary = this.parent.right;

          if (auxiliary.left == null) {
            this.parent.right = auxiliary.right;
          } else if (auxiliary.right == null) {
            this.parent.right = auxiliary.left;
          } else {
            auxiliary = getNode(auxiliary);
          }
        }

      }
    }

    if (auxiliary != null) {
      Console.Write("\n Delete :  " + element);

      auxiliary = null;
    } else {
      Console.Write("\n Delete node " + element + " is not found");
    }
    Console.Write("\n");
  }

  //Display tree element inorder form
  public void inorder(Node head) {

    if (head != null) {

      inorder(head.left);
      //Print node value
      Console.Write("  " + head.data);
      inorder(head.right);
    }
  }




  public static void Main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();

    /* Make A Binary Tree
      -----------------------
              1
             /  \
            2    3
           /    /  \
          6    5    4
           \       /
            8     7 
      */
    //Binary tree nodes
    obj.root = new Node(1);
    obj.root.left = new Node(2);
    obj.root.right = new Node(3);
    obj.root.right.right = new Node(4);
    obj.root.right.right.left = new Node(7);
    obj.root.right.left = new Node(5);
    obj.root.left.left = new Node(6);
    obj.root.left.left.right = new Node(8);
    //Display Tree elements
    obj.inorder(obj.root);

    //Test case
    obj.deleteNode(6);
    obj.inorder(obj.root);

    obj.deleteNode(1);
    obj.inorder(obj.root);

    obj.deleteNode(4);
    obj.inorder(obj.root);


    obj.deleteNode(3);
    obj.inorder(obj.root);


    obj.deleteNode(3);
    obj.inorder(obj.root);
  }
}

Output

  6  8  2  1  5  3  7  4
 Delete : 6 
  8  2  1  5  3  7  4
 Delete : 1 
  2  8  5  3  7  4
 Delete : 4 
  2  8  5  3  7
 Delete : 3 
  2  8  5  7
 Delete node 3 is not found
  2  8  5  7
# Python Program
# Delete a node in binary tree

class Node :

  def __init__(self, value) :
    self.data = value
    self.left = self.right = None
  

class BinaryTree :

  def __init__(self) :
    self.root = None
    self.parent = None
  
  def find_parent(self, head, result, element) :
    if (head != None and self.parent == None) :
      if (element == head.data) :
        self.parent = result
        return
      
      self.find_parent(head.left, head, element)
      self.find_parent(head.right, head, element)
    
  
  def getNode(self, head) :
    auxiliary = head
    temp = None
    while (auxiliary.left != None) :
      temp = auxiliary
      auxiliary = auxiliary.left
    
    temp.left = auxiliary.right
    auxiliary.right = None
    head.data = auxiliary.data
    return auxiliary
  
  def deleteNode(self, element) :
    head = self.root
    if (head == None) :
      return
    
    auxiliary = None
    if (head.data == element) :
      auxiliary = head
      if (head.left == None) :
        self.root = head.right
      elif (head.right == None) :
        self.root = head.left
      else :
        auxiliary = self.getNode(head)
      
    else :
      self.parent = None
      self.find_parent(head, head, element)
      if (self.parent != None) :
        if (self.parent.left != None and self.parent.left.data == element) :
          auxiliary = self.parent.left
          if (auxiliary.left == None) :
            self.parent.left = auxiliary.right
          elif (auxiliary.right == None) :
            self.parent.left = auxiliary.left
          else :
            auxiliary = self.getNode(auxiliary)
          
        elif (self.parent.right != None and self.parent.right.data == element) :
          auxiliary = self.parent.right
          if (auxiliary.left == None) :
            self.parent.right = auxiliary.right
          elif (auxiliary.right == None) :
            self.parent.right = auxiliary.left
          else :
            auxiliary = self.getNode(auxiliary)
          
        
      
    
    if (auxiliary != None) :
      print("\n Delete :  ", element)
      auxiliary = None
    else :
      print("\n Delete node ", element ," is not found")
    
   
  
  def inorder(self, head) :
    if (head != None) :
      self.inorder(head.left)
      print(head.data,end="  ")
      self.inorder(head.right)
    
  
def main() :
  obj = BinaryTree()

  # Make A Binary Tree
  # 
  #          1
  #         /  \
  #        2    3
  #       /    /  \
  #      6    5    4
  #       \       /
  #        8     7
  #  
  obj.root = Node(1)
  obj.root.left = Node(2)
  obj.root.right = Node(3)
  obj.root.right.right = Node(4)
  obj.root.right.right.left = Node(7)
  obj.root.right.left = Node(5)
  obj.root.left.left = Node(6)
  obj.root.left.left.right = Node(8)
  obj.inorder(obj.root)
  obj.deleteNode(6)
  obj.inorder(obj.root)
  obj.deleteNode(1)
  obj.inorder(obj.root)
  obj.deleteNode(4)
  obj.inorder(obj.root)
  obj.deleteNode(3)
  obj.inorder(obj.root)
  obj.deleteNode(3)
  obj.inorder(obj.root)
  

if __name__ == "__main__":
  main()

Output

  6  8  2  1  5  3  7  4
 Delete : 6 
  8  2  1  5  3  7  4
 Delete : 1 
  2  8  5  3  7  4
 Delete : 4 
  2  8  5  3  7
 Delete : 3 
  2  8  5  7
 Delete node 3 is not found
  2  8  5  7
# Ruby Program
# Delete a node in binary tree
class Node 
  attr_reader :data, :left, :right
  attr_accessor :data, :left, :right
  def initialize(value) 
    @data = value
    @left = @right = nil
  end
end

class BinaryTree 
  attr_reader :root, :parent
  attr_accessor :root, :parent
  def initialize() 
    @root = nil
    @parent = nil
  end
  def find_parent(head, result, element) 
    if (head != nil and self.parent == nil) 
      if (element == head.data) 
        self.parent = result
        return
      end
      self.find_parent(head.left, head, element)
      self.find_parent(head.right, head, element)
    end
  end
  def getNode(head) 
    auxiliary = head
    temp = nil
    while (auxiliary.left != nil) 
      temp = auxiliary
      auxiliary = auxiliary.left
    end
    temp.left = auxiliary.right
    auxiliary.right = nil
    head.data = auxiliary.data
    return auxiliary
  end
  def deleteNode(element) 
    head = self.root
    if (head == nil) 
      return
    end
    auxiliary = nil
    if (head.data == element) 
      auxiliary = head
      if (head.left == nil) 
        self.root = head.right
      elsif (head.right == nil) 
        self.root = head.left
      else 
        auxiliary = self.getNode(head)
      end
    else 
      self.parent = nil
      self.find_parent(head, head, element)
      if (self.parent != nil) 
        if (self.parent.left != nil and self.parent.left.data == element) 
          auxiliary = self.parent.left
          if (auxiliary.left == nil) 
            self.parent.left = auxiliary.right
          elsif (auxiliary.right == nil) 
            self.parent.left = auxiliary.left
          else 
            auxiliary = self.getNode(auxiliary)
          end
        elsif (self.parent.right != nil and self.parent.right.data == element) 
          auxiliary = self.parent.right
          if (auxiliary.left == nil) 
            self.parent.right = auxiliary.right
          elsif (auxiliary.right == nil) 
            self.parent.right = auxiliary.left
          else 
            auxiliary = self.getNode(auxiliary)
          end
        end
      end
    end
    if (auxiliary != nil) 
      print("\n Delete  : ", element)
      auxiliary = nil
    else 
      print("\n Delete node ", element ," is not found")
    end
    print("\n")
  end
  def inorder(head) 
    if (head != nil) 
      self.inorder(head.left)
      print("  ", head.data)
      self.inorder(head.right)
    end
  end
end

def main() 
  obj = BinaryTree.new()
  
  # Make A Binary Tree
  # 
  #          1
  #         /  \
  #        2    3
  #       /    /  \
  #      6    5    4
  #       \       /
  #        8     7
  #  
  obj.root = Node.new(1)
  obj.root.left = Node.new(2)
  obj.root.right = Node.new(3)
  obj.root.right.right = Node.new(4)
  obj.root.right.right.left = Node.new(7)
  obj.root.right.left = Node.new(5)
  obj.root.left.left = Node.new(6)
  obj.root.left.left.right = Node.new(8)
  obj.inorder(obj.root)
  obj.deleteNode(6)
  obj.inorder(obj.root)
  obj.deleteNode(1)
  obj.inorder(obj.root)
  obj.deleteNode(4)
  obj.inorder(obj.root)
  obj.deleteNode(3)
  obj.inorder(obj.root)
  obj.deleteNode(3)
  obj.inorder(obj.root)
end
main()

Output

  6  8  2  1  5  3  7  4
 Delete : 6 
  8  2  1  5  3  7  4
 Delete : 1 
  2  8  5  3  7  4
 Delete : 4 
  2  8  5  3  7
 Delete : 3 
  2  8  5  7
 Delete node 3 is not found
  2  8  5  7
<?php
/*
  Php Program
  Delete a node in binary tree
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = $this->right = null;
  }
}
class BinaryTree {
  public $root;
  public $parent;

  function __construct() {
    $this->root = null;
    $this->parent = null;
  }
  public  function find_parent($head, $result, $element) {
    if ($head != null && $this->parent == null) {
      if ($element == $head->data) {
        $this->parent = $result;
        return;
      }
      $this->find_parent($head->left, $head, $element);
      $this->find_parent($head->right, $head, $element);
    }
  }
  public  function getNode($head) {
    $auxiliary = $head;
    $temp = null;
    while ($auxiliary->left != null) {
      $temp = $auxiliary;
      $auxiliary = $auxiliary->left;
    }
    $temp->left = $auxiliary->right;
    $auxiliary->right = null;
    $head->data = $auxiliary->data;
    return $auxiliary;
  }
  public  function deleteNode($element) {
    $head = $this->root;
    if ($head == null) {
      return;
    }
    $auxiliary = null;
    if ($head->data == $element) {
      $auxiliary = $head;
      if ($head->left == null) {
        $this->root = $head->right;
      } else
      if ($head->right == null) {
        $this->root = $head->left;
      } else {
        $auxiliary = $this->getNode($head);
      }
    } else {
      $this->parent = null;
      $this->find_parent($head, $head, $element);
      if ($this->parent != null) {
        if ($this->parent->left != null && $this->parent->left->data == $element) {
          $auxiliary = $this->parent->left;
          if ($auxiliary->left == null) {
            $this->parent->left = $auxiliary->right;
          } else
          if ($auxiliary->right == null) {
            $this->parent->left = $auxiliary->left;
          } else {
            $auxiliary = $this->getNode($auxiliary);
          }
        } else
        if ($this->parent->right != null && $this->parent->right->data == $element) {
          $auxiliary = $this->parent->right;
          if ($auxiliary->left == null) {
            $this->parent->right = $auxiliary->right;
          } else
          if ($auxiliary->right == null) {
            $this->parent->right = $auxiliary->left;
          } else {
            $auxiliary = $this->getNode($auxiliary);
          }
        }
      }
    }
    if ($auxiliary != null) {
      echo("\n Delete :  ". $element);
      $auxiliary = null;
    } else {
      echo("\n Delete node ". $element ." is not found");
    }
    echo("\n");
  }
  public  function inorder($head) {
    if ($head != null) {
      $this->inorder($head->left);
      echo("  ". $head->data);
      $this->inorder($head->right);
    }
  }
}
function main() {
  $obj = new BinaryTree();
  /* Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      6    5    4
       \       /
        8     7 
  */
  $obj->root = new Node(1);
  $obj->root->left = new Node(2);
  $obj->root->right = new Node(3);
  $obj->root->right->right = new Node(4);
  $obj->root->right->right->left = new Node(7);
  $obj->root->right->left = new Node(5);
  $obj->root->left->left = new Node(6);
  $obj->root->left->left->right = new Node(8);
  $obj->inorder($obj->root);
  $obj->deleteNode(6);
  $obj->inorder($obj->root);
  $obj->deleteNode(1);
  $obj->inorder($obj->root);
  $obj->deleteNode(4);
  $obj->inorder($obj->root);
  $obj->deleteNode(3);
  $obj->inorder($obj->root);
  $obj->deleteNode(3);
  $obj->inorder($obj->root);
}
main();

Output

  6  8  2  1  5  3  7  4
 Delete : 6 
  8  2  1  5  3  7  4
 Delete : 1 
  2  8  5  3  7  4
 Delete : 4 
  2  8  5  3  7
 Delete : 3 
  2  8  5  7
 Delete node 3 is not found
  2  8  5  7
/*
  Node JS Program
  Delete a node in binary tree
*/
class Node {
  
  constructor(value) {
    this.data = value;
    this.left = this.right = null;
  }
}
class BinaryTree {

  constructor() {
    this.root = null;
    this.parent = null;
  }
  find_parent(head, result, element) {
    if (head != null && this.parent == null) {
      if (element == head.data) {
        this.parent = result;
        return;
      }
      this.find_parent(head.left, head, element);
      this.find_parent(head.right, head, element);
    }
  }
  getNode(head) {
    var auxiliary = head;
    var temp = null;
    while (auxiliary.left != null) {
      temp = auxiliary;
      auxiliary = auxiliary.left;
    }
    temp.left = auxiliary.right;
    auxiliary.right = null;
    head.data = auxiliary.data;
    return auxiliary;
  }
  deleteNode(element) {
    var head = this.root;
    if (head == null) {
      return;
    }
    var auxiliary = null;
    if (head.data == element) {
      auxiliary = head;
      if (head.left == null) {
        this.root = head.right;
      } else
      if (head.right == null) {
        this.root = head.left;
      } else {
        auxiliary = this.getNode(head);
      }
    } else {
      this.parent = null;
      this.find_parent(head, head, element);
      if (this.parent != null) {
        if (this.parent.left != null && this.parent.left.data == element) {
          auxiliary = this.parent.left;
          if (auxiliary.left == null) {
            this.parent.left = auxiliary.right;
          } else
          if (auxiliary.right == null) {
            this.parent.left = auxiliary.left;
          } else {
            auxiliary = this.getNode(auxiliary);
          }
        } else
        if (this.parent.right != null && this.parent.right.data == element) {
          auxiliary = this.parent.right;
          if (auxiliary.left == null) {
            this.parent.right = auxiliary.right;
          } else
          if (auxiliary.right == null) {
            this.parent.right = auxiliary.left;
          } else {
            auxiliary = this.getNode(auxiliary);
          }
        }
      }
    }
    if (auxiliary != null) {
      process.stdout.write("\n Delete :  " + element);
      auxiliary = null;
    } else {
      process.stdout.write("\n Delete node " + element + " is not found");
    }
    process.stdout.write("\n");
  }
  inorder(head) {
    if (head != null) {
      this.inorder(head.left);
      process.stdout.write("  " + head.data);
      this.inorder(head.right);
    }
  }
}
function main() {
  var obj = new BinaryTree();
  /* Make A Binary Tree
    -----------------------
          1
         /  \
        2    3
       /    /  \
      6    5    4
       \       /
        8     7 
    */
  obj.root = new Node(1);
  obj.root.left = new Node(2);
  obj.root.right = new Node(3);
  obj.root.right.right = new Node(4);
  obj.root.right.right.left = new Node(7);
  obj.root.right.left = new Node(5);
  obj.root.left.left = new Node(6);
  obj.root.left.left.right = new Node(8);
  obj.inorder(obj.root);
  obj.deleteNode(6);
  obj.inorder(obj.root);
  obj.deleteNode(1);
  obj.inorder(obj.root);
  obj.deleteNode(4);
  obj.inorder(obj.root);
  obj.deleteNode(3);
  obj.inorder(obj.root);
  obj.deleteNode(3);
  obj.inorder(obj.root);
}
main();

Output

  6  8  2  1  5  3  7  4
 Delete : 6 
  8  2  1  5  3  7  4
 Delete : 1 
  2  8  5  3  7  4
 Delete : 4 
  2  8  5  3  7
 Delete : 3 
  2  8  5  7
 Delete node 3 is not found
  2  8  5  7
/*
  Swift 4 Program
  Delete a node in binary tree
*/
class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
 
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinaryTree {
  var root: Node? ;
  var parent: Node? ;
  init() {
    self.root = nil;
    self.parent = nil;
  }
  func find_parent(_ head: Node? , _ result : Node? , _ element : Int) {
    if (head != nil && self.parent == nil) {
      if (element == head!.data) {
        self.parent = result;
        return;
      }
      self.find_parent(head!.left, head, element);
      self.find_parent(head!.right, head, element);
    }
  }
  func getNode(_ head: Node? ) -> Node? {
    var auxiliary: Node? = head;
    var temp: Node? = nil;
    while (auxiliary!.left != nil) {
      temp = auxiliary;
      auxiliary = auxiliary!.left;
    }
    temp!.left = auxiliary!.right;
    auxiliary!.right = nil;
    head!.data = auxiliary!.data;
    return auxiliary;
  }
  func deleteNode(_ element: Int) {
    let head: Node? = self.root;
    if (head == nil) {
      return;
    }
    var auxiliary: Node? = nil;
    if (head!.data == element) {
      auxiliary = head;
      if (head!.left == nil) {
        self.root = head!.right;
      } else
      if (head!.right == nil) {
        self.root = head!.left;
      } else {
        auxiliary = self.getNode(head);
      }
    } else {
      self.parent = nil;
      self.find_parent(head, head, element);
      if (self.parent != nil) {
        if (self.parent!.left != nil && self.parent!.left!.data == element) {
          auxiliary = self.parent!.left;
          if (auxiliary!.left == nil) {
            self.parent!.left = auxiliary!.right;
          } else
          if (auxiliary!.right == nil) {
            self.parent!.left = auxiliary!.left;
          } else {
            auxiliary = self.getNode(auxiliary);
          }
        } else
        if (self.parent!.right != nil && self.parent!.right!.data == element) {
          auxiliary = self.parent!.right;
          if (auxiliary!.left == nil) {
            self.parent!.right = auxiliary!.right;
          } else
          if (auxiliary!.right == nil) {
            self.parent!.right = auxiliary!.left;
          } else {
            auxiliary = self.getNode(auxiliary);
          }
        }
      }
    }
    if (auxiliary != nil) {
      print("\n Delete :  ", element);
      auxiliary = nil;
    } else {
      print("\n Delete node ", element , " is not found");
    }
  
  }
  func inorder(_ head: Node? ) {
    if (head != nil) {
      self.inorder(head!.left);
      print(head!.data,terminator : "  ");
      self.inorder(head!.right);
    }
  }
}
func main() {
  let obj: BinaryTree = BinaryTree();
  /* Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      6    5    4
       \       /
        8     7 
  */
  obj.root = Node(1);
  obj.root!.left = Node(2);
  obj.root!.right = Node(3);
  obj.root!.right!.right = Node(4);
  obj.root!.right!.right!.left = Node(7);
  obj.root!.right!.left = Node(5);
  obj.root!.left!.left = Node(6);
  obj.root!.left!.left!.right = Node(8);
  obj.inorder(obj.root);
  obj.deleteNode(6);
  obj.inorder(obj.root);
  obj.deleteNode(1);
  obj.inorder(obj.root);
  obj.deleteNode(4);
  obj.inorder(obj.root);
  obj.deleteNode(3);
  obj.inorder(obj.root);
  obj.deleteNode(3);
  obj.inorder(obj.root);
}
main();

Output

  6  8  2  1  5  3  7  4
 Delete : 6 
  8  2  1  5  3  7  4
 Delete : 1 
  2  8  5  3  7  4
 Delete : 4 
  2  8  5  3  7
 Delete : 3 
  2  8  5  7
 Delete node 3 is not found
  2  8  5  7




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment