Posted on by Kalkicode
Code Binary Tree

# Delete a node in binary tree

The problem at hand involves deleting a node from a binary tree. A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. Deleting a node from a binary tree requires reorganizing the tree while maintaining its structure and properties.

## Problem Statement and Description

Given a binary tree and a value to be deleted, the task is to implement a function that removes the node with the specified value from the tree. The challenge lies in correctly handling the various cases that can arise during deletion, such as whether the node to be deleted has zero, one, or two children.

## Example

Consider the following binary tree:

``````
1
/ \
2   3
/   / \
6   5   4
\     /
8   7``````

We want to delete nodes with values: 6, 1, 4, and 3.

After deleting 6:

``````
1
/ \
2   3
/   / \
8   5   4
/
7
``````

After deleting 1:

``````
8
/ \
2   3
/ \
5   4
/
7
``````

After deleting 4:

``````
8
/ \
2   3
/ \
5   7
``````

After deleting 3 :

``````
8
/ \
2   5
\
7
``````

## Idea to Solve the Problem

To solve this problem, we need to follow these steps:

1. Search for the Node to Delete

Traverse the tree to locate the node with the value to be deleted.

2. Handle Different Cases
• If the node to be deleted has no children, simply remove the node.
• If the node to be deleted has one child, replace the node with its child.
• If the node to be deleted has two children, find the in-order successor (or predecessor) of the node, copy its value to the node to be deleted, and then recursively delete the in-order successor (or predecessor).
3. Update Parent Pointers

Adjust the parent pointers to reflect the changes in the tree structure after deletion.

## Standard Pseudocode

Here's a high-level pseudocode representation of the algorithm to delete a node from a binary tree:

``````
DeleteNode(root, value):
if root is NULL:
return NULL

if value is less than root's value:
root.left = DeleteNode(root.left, value)
else if value is greater than root's value:
root.right = DeleteNode(root.right, value)
else:
if root has no left child:
temp = root.right
free root
return temp
else if root has no right child:
temp = root.left
free root
return temp
temp = FindMinimumValueNode(root.right)
root.value = temp.value
root.right = DeleteNode(root.right, temp.value)

return root
``````

## Algorithm Explanation

2. Recursively traverse the tree to locate the node to be deleted.
3. If the node is found:
• Handle the case where the node has no children or only one child.
• For the case where the node has two children, find the in-order successor (minimum value node in the right subtree), copy its value to the current node, and recursively delete the in-order successor.
4. After the deletion is complete, return the modified root of the tree.

## 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);

//When deleted node are exist

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

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

}
}

if (auxiliary != NULL) {
printf("\n Delete : %d ", element);
free(auxiliary);
auxiliary = NULL;
} else {
}
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
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) {
this->parent = result;
return;
}
}
}
Node *auxiliary = head, *temp = NULL;
while (auxiliary->left != NULL) {
temp = auxiliary;
auxiliary = auxiliary->left;
}
temp->left = auxiliary->right;
auxiliary->right = NULL;
return auxiliary;
}
void deleteNode(int element) {
return;
}
Node *auxiliary = NULL;
} else
} else {
}
} else {
this->parent = NULL;
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";
}
cout << "  " << head->data;
}
}
};

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
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) {
this.parent = result;
return;
}
}

}
//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

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

return;
}

Node auxiliary = null;

//When no left sub tree

} else if (head.right == null) {
//When no right sub tree
} else {
}
} else {

this.parent = null;
//Find parent of deleted node

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");
}

//Display tree element inorder form

//Print node value
}
}

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
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) {
this.parent = result;
return;
}
}

}
//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

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

return;
}

Node auxiliary = null;

//When no left sub tree

} else if (head.right == null) {
//When no right sub tree
} else {
}
} else {

this.parent = null;
//Find parent of deleted node

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");
}

//Display tree element inorder form

//Print node value
}
}

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
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) :
self.parent = result
return

temp = None
while (auxiliary.left != None) :
temp = auxiliary
auxiliary = auxiliary.left

temp.left = auxiliary.right
auxiliary.right = None
return auxiliary

def deleteNode(self, element) :
return

auxiliary = None
else :

else :
self.parent = None
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 :

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
2  8  5  7``````
``````# Ruby Program
# Delete a node in binary tree
class Node
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = @right = nil
end
end

class BinaryTree
attr_accessor :root, :parent
def initialize()
@root = nil
@parent = nil
end
if (head != nil and self.parent == nil)
self.parent = result
return
end
end
end
temp = nil
while (auxiliary.left != nil)
temp = auxiliary
auxiliary = auxiliary.left
end
temp.left = auxiliary.right
auxiliary.right = nil
return auxiliary
end
def deleteNode(element)
return
end
auxiliary = nil
else
end
else
self.parent = nil
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
end
print("\n")
end
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
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) {
\$this->parent = \$result;
return;
}
}
}
\$temp = null;
while (\$auxiliary->left != null) {
\$temp = \$auxiliary;
\$auxiliary = \$auxiliary->left;
}
\$temp->left = \$auxiliary->right;
\$auxiliary->right = null;
return \$auxiliary;
}
public  function deleteNode(\$element) {
return;
}
\$auxiliary = null;
} else
} else {
}
} else {
\$this->parent = null;
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");
}
}
}
}
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
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;
}
if (head != null && this.parent == null) {
this.parent = result;
return;
}
}
}
var temp = null;
while (auxiliary.left != null) {
temp = auxiliary;
auxiliary = auxiliary.left;
}
temp.left = auxiliary.right;
auxiliary.right = null;
return auxiliary;
}
deleteNode(element) {
return;
}
var auxiliary = null;
} else
} else {
}
} else {
this.parent = null;
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");
}
}
}
}
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
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) {
self.parent = result;
return;
}
}
}
func getNode(_ head: Node? ) -> Node? {
var temp: Node? = nil;
while (auxiliary!.left != nil) {
temp = auxiliary;
auxiliary = auxiliary!.left;
}
temp!.left = auxiliary!.right;
auxiliary!.right = nil;
return auxiliary;
}
func deleteNode(_ element: Int) {
return;
}
var auxiliary: Node? = nil;
} else
} else {
}
} else {
self.parent = nil;
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 {
}

}
func inorder(_ head: Node? ) {
}
}
}
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
2  8  5  7``````

## Time Complexity

The time complexity of the mentioned code is primarily determined by the tree traversal during the deletion operation, which is O(h), where 'h' is the height of the tree. In the worst case, when the tree is unbalanced and resembles a linked list, the time complexity becomes O(n), where 'n' is the number of nodes in the tree. However, in a balanced binary tree, the time complexity is closer to O(log n), where 'n' is the number of nodes.

This complexity arises because in the worst case, the algorithm may need to traverse the height of the tree twice: once during the search for the node to be deleted and again during the recursive deletion process.

## 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.

Categories
Relative Post