Posted on by Kalkicode
Code Queue

# Delete entire nodes of a binary tree

The problem to be tackled in this scenario involves the deletion of entire nodes from a binary tree. The solution focuses on using a queue-based approach for efficiently deleting nodes in a level-order manner.

## Problem Statement

Given a binary tree, the task is to delete all its nodes efficiently, using a queue to traverse the tree in a level-order fashion.

## Example Scenario

Consider the following binary tree:

``````	      10
/   \
6     8
/     / \
2     7   2
/       \   \
9        -1   9``````

After deleting all the nodes, the output should be:

`````` Delete Node : 10
Delete Node : 6
Delete Node : 8
Delete Node : 2
Delete Node : 7
Delete Node : 2
Delete Node : 9
Delete Node : -1
Delete Node : 9``````

## Idea to Solve the Problem

To solve this problem efficiently, we can use a queue-based approach. We start by adding the root node to the queue. Then, we iteratively remove nodes from the queue, delete them, and enqueue their left and right children if they exist. This process continues until the queue becomes empty.

## Pseudocode

``````struct Node *delete_all_nodes(struct Node *root)
{
if (root is NULL)
{
// Handle the case of an empty tree
return NULL;
}
else
{
// Create a queue for level-order traversal
// Enqueue the root node

// Iterate while the queue is not empty
while (the queue is not empty)
{
// Dequeue the front node

// Enqueue left and right children if they exist

// Delete the dequeued node

// Print the deleted node's value
}

return NULL;
}
}``````

## Algorithm Explanation

1. Implement the `delete_all_nodes` function that takes the root node of the binary tree as input.
2. Check if the tree is empty. If it is, handle the case and return NULL.
3. Create a queue using the provided `queue_node` function.
4. Enqueue the root node into the queue.
5. Start a loop that continues as long as the queue is not empty.
6. Inside the loop, dequeue the front node from the queue.
7. If the dequeued node has left and/or right children, enqueue them into the queue.
8. Delete the dequeued node by freeing its memory.
9. Print the value of the deleted node.
10. After the loop ends, all nodes will be deleted.
11. Return NULL to indicate the tree is empty.

## Code Solution

``````/*
C Program
Delete entire nodes of a binary tree
Using queue
*/
#include <stdio.h>

#include <stdlib.h>

//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//Define Custom queue
struct MyQueue
{
struct Node *element;
struct MyQueue *next;
};
//This is creating a binary tree node and return this
{
// Create dynamic 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;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}
//Recursive function
//Display preorder view of binary tree
void pre_order(struct Node *node)
{
if (node != NULL)
{
//Print node value
printf("  %d", node->data);
pre_order(node->left);
pre_order(node->right);
}
}
//Create a MyQueue element and return this reference
struct MyQueue *queue_node(struct Node *tree_node)
{
struct MyQueue *MyQueue_node = (struct MyQueue *) malloc(sizeof(struct MyQueue));
if (MyQueue_node != NULL)
{
//set pointer values
MyQueue_node->element = tree_node;
MyQueue_node->next = NULL;
}
else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
return MyQueue_node;
}
//Remove a MyQueue elements
{
{
//Get a deleted node
//Visit to next node of MyQueue
remove->element = NULL;
remove->next = NULL;
//free node
free(remove);
remove = NULL;
}
}
// Deleting all nodes in given tree in from top to bottom direction level by level
// Using queue
struct Node *delete_all_nodes(struct Node *root)
{
if (root == NULL)
{
printf("\nEmpty Tree\n");
return NULL;
}
else
{
// Before delete, display tree elements
printf("\n  Tree Element \n");
pre_order(root);
//Make MyQueue variables
struct MyQueue *tail = NULL;
//Get first node of tree
struct Node *auxiliary = root;
//initial tail is same to head of queue
//iterate the MyQueue elements
{
//Get current head element of MyQueue
if (auxiliary->left != NULL)
{
tail->next = queue_node(auxiliary->left);
tail = tail->next;
}
if (auxiliary->right != NULL)
{
tail->next = queue_node(auxiliary->right);
tail = tail->next;
}
auxiliary->left = NULL;
//Remove element of MyQueue
printf("\n Delete Node : %d", auxiliary->data);
//Deleted tree element
auxiliary->left = NULL;
auxiliary->right = NULL;
free(auxiliary);
auxiliary = NULL;
}
tail = NULL;
return NULL;
}
}
int main()
{
struct Node *root = NULL;
/*
Construct Binary Tree
-----------------------
10
/   \
6     8
/     / \
2     7   2
/       \   \
9        -1   9
*/
//Test Process
root = delete_all_nodes(root);
return 0;
}``````

#### Output

``````  Tree Element
10  6  2  9  8  7  -1  2  9
Delete Node : 10
Delete Node : 6
Delete Node : 8
Delete Node : 2
Delete Node : 7
Delete Node : 2
Delete Node : 9
Delete Node : -1
Delete Node : 9``````
``````// Java Program
// Delete entire nodes of a binary tree
// Using queue

//Binary Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
//Define Custom queue
class MyQueue
{
public Node element;
public MyQueue next;
public MyQueue(Node element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
public Node root;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
}
//Recursive function
//Display preorder view of binary tree
public void pre_order(Node node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
pre_order(node.left);
pre_order(node.right);
}
}
//Remove a dequeue element
{
{
//remove node
return temp;
}
return null;
}
// Deleting all nodes in given tree in from top to bottom direction level by level
// Using queue
public void delete_all_nodes()
{
if (this.root == null)
{
System.out.print("\nEmpty Tree\n");
}
else
{
// Before delete, display tree elements
System.out.print("\n Tree Element \n");
pre_order(this.root);
//Make MyQueue variables
//initial tail is same to head of queue
//Get first node of tree
Node auxiliary = this.root;
this.root = null;
//iterate the MyQueue elements
{
//Get current head element of MyQueue
if (auxiliary.left != null)
{
tail.next = new MyQueue(auxiliary.left);
tail = tail.next;
}
if (auxiliary.right != null)
{
tail.next = new MyQueue(auxiliary.right);
tail = tail.next;
}
auxiliary.left = null;
//Remove element of MyQueue
System.out.print("\n Delete Node : " + auxiliary.data);
//Deleted tree element
auxiliary.left = null;
auxiliary.right = null;
auxiliary = null;
}
tail = null;
}
}
public static void main(String[] args)
{
//Make object
BinaryTree obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
6     8
/     / \
2     7   2
/       \   \
9        -1   9
*/
obj.root = new Node(10);
obj.root.left = new Node(6);
obj.root.left.left = new Node(2);
obj.root.right = new Node(8);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(7);
obj.root.left.left.left = new Node(9);
obj.root.right.left.right = new Node(-1);
obj.root.right.right.right = new Node(9);
//Test Process
obj.delete_all_nodes();
}
}``````

#### Output

`````` Tree Element
10 6 2 9 8 7 -1 2 9
Delete Node : 10
Delete Node : 6
Delete Node : 8
Delete Node : 2
Delete Node : 7
Delete Node : 2
Delete Node : 9
Delete Node : -1
Delete Node : 9``````
``````//Include header file
#include <iostream>
using namespace std;

// C++ Program
// Delete entire nodes of a binary tree
// Using queue

//Binary Tree node
class Node
{
public: int data;
Node *left;
Node *right;
Node(int data)
{
//set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
//Define Custom queue
class MyQueue
{
public: Node *element;
MyQueue *next;
MyQueue(Node *element)
{
this->element = element;
this->next = NULL;
}
};
class BinaryTree
{
public: Node *root;
BinaryTree()
{
//set initial tree root to null
this->root = NULL;
}
//Recursive function
//Display preorder view of binary tree
void pre_order(Node *node)
{
if (node != NULL)
{
//Print node value
cout << " " << node->data;
this->pre_order(node->left);
this->pre_order(node->right);
}
}
//Remove a dequeue element
{
{
//remove node
return temp;
}
return NULL;
}
// Deleting all nodes in given tree in from top to bottom direction level by level
// Using queue
void delete_all_nodes()
{
if (this->root == NULL)
{
cout << "\nEmpty Tree\n";
}
else
{
// Before delete, display tree elements
cout << "\n Tree Element \n";
this->pre_order(this->root);
//Make MyQueue variables
//initial tail is same to head of queue
//Get first node of tree
Node *auxiliary = this->root;
this->root = NULL;
//iterate the MyQueue elements
{
//Get current head element of MyQueue
if (auxiliary->left != NULL)
{
tail->next = new MyQueue(auxiliary->left);
tail = tail->next;
}
if (auxiliary->right != NULL)
{
tail->next = new MyQueue(auxiliary->right);
tail = tail->next;
}
auxiliary->left = NULL;
//Remove element of MyQueue
cout << "\n Delete Node : " << auxiliary->data;
//Deleted tree element
auxiliary->left = NULL;
auxiliary->right = NULL;
delete auxiliary;
auxiliary = NULL;
}
tail = NULL;
}
}
};
int main()
{
//Make object
BinaryTree obj = BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
6     8
/     / \
2     7   2
/       \   \
9        -1   9
*/
obj.root = new Node(10);
obj.root->left = new Node(6);
obj.root->left->left = new Node(2);
obj.root->right = new Node(8);
obj.root->right->right = new Node(2);
obj.root->right->left = new Node(7);
obj.root->left->left->left = new Node(9);
obj.root->right->left->right = new Node(-1);
obj.root->right->right->right = new Node(9);
//Test Process
obj.delete_all_nodes();
return 0;
}``````

#### Output

`````` Tree Element
10 6 2 9 8 7 -1 2 9
Delete Node : 10
Delete Node : 6
Delete Node : 8
Delete Node : 2
Delete Node : 7
Delete Node : 2
Delete Node : 9
Delete Node : -1
Delete Node : 9``````
``````//Include namespace system
using System;

// C# Program
// Delete entire nodes of a binary tree
// Using queue

//Binary Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
//Define Custom queue
class MyQueue
{
public Node element;
public MyQueue next;
public MyQueue(Node element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
public Node root;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
}
//Recursive function
//Display preorder view of binary tree
public void pre_order(Node node)
{
if (node != null)
{
//Print node value
Console.Write(" " + node.data);
pre_order(node.left);
pre_order(node.right);
}
}
//Remove a dequeue element
{
{
//remove node
return temp;
}
return null;
}
// Deleting all nodes in given tree in from top to bottom direction level by level
// Using queue
public void delete_all_nodes()
{
if (this.root == null)
{
Console.Write("\nEmpty Tree\n");
}
else
{
// Before delete, display tree elements
Console.Write("\n Tree Element \n");
pre_order(this.root);
//Make MyQueue variables
//initial tail is same to head of queue
//Get first node of tree
Node auxiliary = this.root;
this.root = null;
//iterate the MyQueue elements
{
//Get current head element of MyQueue
if (auxiliary.left != null)
{
tail.next = new MyQueue(auxiliary.left);
tail = tail.next;
}
if (auxiliary.right != null)
{
tail.next = new MyQueue(auxiliary.right);
tail = tail.next;
}
auxiliary.left = null;
//Remove element of MyQueue
Console.Write("\n Delete Node : " + auxiliary.data);
//Deleted tree element
auxiliary.left = null;
auxiliary.right = null;
auxiliary = null;
}
tail = null;
}
}
public static void Main(String[] args)
{
//Make object
BinaryTree obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
6     8
/     / \
2     7   2
/       \   \
9        -1   9
*/
obj.root = new Node(10);
obj.root.left = new Node(6);
obj.root.left.left = new Node(2);
obj.root.right = new Node(8);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(7);
obj.root.left.left.left = new Node(9);
obj.root.right.left.right = new Node(-1);
obj.root.right.right.right = new Node(9);
//Test Process
obj.delete_all_nodes();
}
}``````

#### Output

`````` Tree Element
10 6 2 9 8 7 -1 2 9
Delete Node : 10
Delete Node : 6
Delete Node : 8
Delete Node : 2
Delete Node : 7
Delete Node : 2
Delete Node : 9
Delete Node : -1
Delete Node : 9``````
``````<?php
// Php Program
// Delete entire nodes of a binary tree
// Using queue

//Binary Tree node
class Node
{
public \$data;
public \$left;
public \$right;

function __construct(\$data)
{
//set node value
\$this->data = \$data;
\$this->left = null;
\$this->right = null;
}
}
//Define Custom queue
class MyQueue
{
public \$element;
public \$next;

function __construct(\$element)
{
\$this->element = \$element;
\$this->next = null;
}
}
class BinaryTree
{
public \$root;

function __construct()
{
//set initial tree root to null
\$this->root = null;
}
//Recursive function
//Display preorder view of binary tree
public	function pre_order(\$node)
{
if (\$node != null)
{
//Print node value
echo " ". \$node->data;
\$this->pre_order(\$node->left);
\$this->pre_order(\$node->right);
}
}
//Remove a dequeue element
{
{
//remove node
return \$temp;
}
return null;
}
// Deleting all nodes in given tree in from top to bottom direction level by level
// Using queue
public	function delete_all_nodes()
{
if (\$this->root == null)
{
echo "\nEmpty Tree\n";
}
else
{
// Before delete, display tree elements
echo "\n Tree Element \n";
\$this->pre_order(\$this->root);
//Make MyQueue variables
//initial tail is same to head of queue
//Get first node of tree
\$auxiliary = \$this->root;
\$this->root = null;
//iterate the MyQueue elements
{
//Get current head element of MyQueue
if (\$auxiliary->left != null)
{
\$tail->next = new MyQueue(\$auxiliary->left);
\$tail = \$tail->next;
}
if (\$auxiliary->right != null)
{
\$tail->next = new MyQueue(\$auxiliary->right);
\$tail = \$tail->next;
}
\$auxiliary->left = null;
//Remove element of MyQueue
echo "\n Delete Node : ". \$auxiliary->data;
//Deleted tree element
\$auxiliary->left = null;
\$auxiliary->right = null;
\$auxiliary = null;
}
\$tail = null;
}
}
}

function main()
{
//Make object
\$obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
6     8
/     / \
2     7   2
/       \   \
9        -1   9
*/
\$obj->root = new Node(10);
\$obj->root->left = new Node(6);
\$obj->root->left->left = new Node(2);
\$obj->root->right = new Node(8);
\$obj->root->right->right = new Node(2);
\$obj->root->right->left = new Node(7);
\$obj->root->left->left->left = new Node(9);
\$obj->root->right->left->right = new Node(-1);
\$obj->root->right->right->right = new Node(9);
//Test Process
\$obj->delete_all_nodes();
}
main();``````

#### Output

`````` Tree Element
10 6 2 9 8 7 -1 2 9
Delete Node : 10
Delete Node : 6
Delete Node : 8
Delete Node : 2
Delete Node : 7
Delete Node : 2
Delete Node : 9
Delete Node : -1
Delete Node : 9``````
``````// Node Js Program
// Delete entire nodes of a binary tree
// Using queue

//Binary Tree node
class Node
{
constructor(data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
//Define Custom queue
class MyQueue
{
constructor(element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
constructor()
{
//set initial tree root to null
this.root = null;
}
//Recursive function
//Display preorder view of binary tree
pre_order(node)
{
if (node != null)
{
//Print node value
process.stdout.write(" " + node.data);
this.pre_order(node.left);
this.pre_order(node.right);
}
}
//Remove a dequeue element
{
{
//remove node
return temp;
}
return null;
}
// Deleting all nodes in given tree in from top to bottom direction level by level
// Using queue
delete_all_nodes()
{
if (this.root == null)
{
process.stdout.write("\nEmpty Tree\n");
}
else
{
// Before delete, display tree elements
process.stdout.write("\n Tree Element \n");
this.pre_order(this.root);
//Make MyQueue variables
//initial tail is same to head of queue
//Get first node of tree
var auxiliary = this.root;
this.root = null;
//iterate the MyQueue elements
{
//Get current head element of MyQueue
if (auxiliary.left != null)
{
tail.next = new MyQueue(auxiliary.left);
tail = tail.next;
}
if (auxiliary.right != null)
{
tail.next = new MyQueue(auxiliary.right);
tail = tail.next;
}
auxiliary.left = null;
//Remove element of MyQueue
process.stdout.write("\n Delete Node : " + auxiliary.data);
//Deleted tree element
auxiliary.left = null;
auxiliary.right = null;
auxiliary = null;
}
tail = null;
}
}
}

function main()
{
//Make object
var obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
6     8
/     / \
2     7   2
/       \   \
9        -1   9
*/
obj.root = new Node(10);
obj.root.left = new Node(6);
obj.root.left.left = new Node(2);
obj.root.right = new Node(8);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(7);
obj.root.left.left.left = new Node(9);
obj.root.right.left.right = new Node(-1);
obj.root.right.right.right = new Node(9);
//Test Process
obj.delete_all_nodes();
}
main();``````

#### Output

`````` Tree Element
10 6 2 9 8 7 -1 2 9
Delete Node : 10
Delete Node : 6
Delete Node : 8
Delete Node : 2
Delete Node : 7
Delete Node : 2
Delete Node : 9
Delete Node : -1
Delete Node : 9``````
``````#  Python 3 Program
#  Delete entire nodes of a binary tree
#  Using queue

# Binary Tree node
class Node :

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

# Define Custom queue
class MyQueue :

def __init__(self, element) :
self.element = element
self.next = None

class BinaryTree :

def __init__(self) :
# set initial tree root to null
self.root = None

# Recursive function
# Display preorder view of binary tree
def pre_order(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.pre_order(node.left)
self.pre_order(node.right)

# Remove a dequeue element
# remove node
return temp

return None

#  Deleting all nodes in given tree in from top to bottom direction level by level
#  Using queue
def delete_all_nodes(self) :
if (self.root == None) :
print("\nEmpty Tree\n", end = "")
else :
#  Before delete, display tree elements
print("\n Tree Element \n", end = "")
self.pre_order(self.root)
# Make MyQueue variables
# Add first node into MyQueue
# initial tail is same to head of queue
# Get first node of tree
auxiliary = self.root
self.root = None
# iterate the MyQueue elements
# Get current head element of MyQueue
if (auxiliary.left != None) :
# Add new left child node
tail.next = MyQueue(auxiliary.left)
tail = tail.next

if (auxiliary.right != None) :
# Add new right child node
tail.next = MyQueue(auxiliary.right)
tail = tail.next

auxiliary.left = None
# Remove element of MyQueue
print("\n Delete Node : ", auxiliary.data, end = "")
# Deleted tree element
auxiliary.left = None
auxiliary.right = None
auxiliary = None

tail = None

def main() :
# Make object
obj = BinaryTree()
#
# 		Construct Binary Tree
# 		-----------------------
# 		      10
# 		     /   \
# 		    6     8
# 		   /     / \
# 		  2     7   2
# 		 /       \   \
# 		9        -1   9
#

obj.root = Node(10)
obj.root.left = Node(6)
obj.root.left.left = Node(2)
obj.root.right = Node(8)
obj.root.right.right = Node(2)
obj.root.right.left = Node(7)
obj.root.left.left.left = Node(9)
obj.root.right.left.right = Node(-1)
obj.root.right.right.right = Node(9)
# Test Process
obj.delete_all_nodes()

if __name__ == "__main__": main()``````

#### Output

`````` Tree Element
10  6  2  9  8  7  -1  2  9
Delete Node :  10
Delete Node :  6
Delete Node :  8
Delete Node :  2
Delete Node :  7
Delete Node :  2
Delete Node :  9
Delete Node :  -1
Delete Node :  9``````
``````#  Ruby Program
#  Delete entire nodes of a binary tree
#  Using queue

# Binary Tree node
class Node
# Define the accessor and reader of class Node
attr_accessor :data, :left, :right

def initialize(data)
# set node value
self.data = data
self.left = nil
self.right = nil
end
end

# Define Custom queue
class MyQueue
# Define the accessor and reader of class MyQueue
attr_accessor :element, :next

def initialize(element)
self.element = element
self.next = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root

def initialize()
# set initial tree root to null
self.root = nil
end
# Recursive function
# Display preorder view of binary tree
def pre_order(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.pre_order(node.left)
self.pre_order(node.right)
end
end
# Remove a dequeue element
# remove node
return temp
end
return nil
end
#  Deleting all nodes in given tree in from top to bottom direction level by level
#  Using queue
def delete_all_nodes()
if (self.root == nil)
print("\nEmpty Tree\n")
else
#  Before delete, display tree elements
print("\n Tree Element \n")
self.pre_order(self.root)
# Make MyQueue variables
# Add first node into MyQueue
# initial tail is same to head of queue
# Get first node of tree
auxiliary = self.root
self.root = nil
# iterate the MyQueue elements
# Get current head element of MyQueue
if (auxiliary.left != nil)
# Add new left child node
tail.next = MyQueue.new(auxiliary.left)
tail = tail.next
end
if (auxiliary.right != nil)
# Add new right child node
tail.next = MyQueue.new(auxiliary.right)
tail = tail.next
end
auxiliary.left = nil
# Remove element of MyQueue
print("\n Delete Node : ", auxiliary.data)
# Deleted tree element
auxiliary.left = nil
auxiliary.right = nil
auxiliary = nil
end
tail = nil
end
end
end
def main()
# Make object
obj = BinaryTree.new()
#
# 		Construct Binary Tree
# 		-----------------------
# 		      10
# 		     /   \
# 		    6     8
# 		   /     / \
# 		  2     7   2
# 		 /       \   \
# 		9        -1   9
#

obj.root = Node.new(10)
obj.root.left = Node.new(6)
obj.root.left.left = Node.new(2)
obj.root.right = Node.new(8)
obj.root.right.right = Node.new(2)
obj.root.right.left = Node.new(7)
obj.root.left.left.left = Node.new(9)
obj.root.right.left.right = Node.new(-1)
obj.root.right.right.right = Node.new(9)
# Test Process
obj.delete_all_nodes()
end
main()``````

#### Output

`````` Tree Element
10 6 2 9 8 7 -1 2 9
Delete Node : 10
Delete Node : 6
Delete Node : 8
Delete Node : 2
Delete Node : 7
Delete Node : 2
Delete Node : 9
Delete Node : -1
Delete Node : 9``````
``````// Scala Program
// Delete entire nodes of a binary tree
// Using queue

//Binary Tree node
class Node(var data: Int,
var left: Node,
var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
//Define Custom queue
class MyQueue(var element: Node,
var next: MyQueue)
{
def this(element: Node)
{
this(element, null);
}
}
class BinaryTree(var root: Node)
{
def this()
{
this(null);
}
//Recursive function
//Display preorder view of binary tree
def pre_order(node: Node): Unit = {
if (node != null)
{
//Print node value
print(" " + node.data);
pre_order(node.left);
pre_order(node.right);
}
}
//Remove a dequeue element
def dequeue(head: MyQueue): MyQueue = {
{
//remove node
return temp;
}
return null;
}
// Deleting all nodes in given tree in from top to bottom direction level by level
// Using queue
def delete_all_nodes(): Unit = {
if (this.root == null)
{
print("\nEmpty Tree\n");
}
else
{
// Before delete, display tree elements
print("\n Tree Element \n");
pre_order(this.root);
//Make MyQueue variables
var head: MyQueue = new MyQueue(this.root);
//initial tail is same to head of queue
//Get first node of tree
var auxiliary: Node = this.root;
this.root = null;
//iterate the MyQueue elements
{
//Get current head element of MyQueue
if (auxiliary.left != null)
{
tail.next = new MyQueue(auxiliary.left);
tail = tail.next;
}
if (auxiliary.right != null)
{
tail.next = new MyQueue(auxiliary.right);
tail = tail.next;
}
auxiliary.left = null;
//Remove element of MyQueue
print("\n Delete Node : " + auxiliary.data);
//Deleted tree element
auxiliary.left = null;
auxiliary.right = null;
auxiliary = null;
}
tail = null;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object
var obj: BinaryTree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
6     8
/     / \
2     7   2
/       \   \
9        -1   9
*/
obj.root = new Node(10);
obj.root.left = new Node(6);
obj.root.left.left = new Node(2);
obj.root.right = new Node(8);
obj.root.right.right = new Node(2);
obj.root.right.left = new Node(7);
obj.root.left.left.left = new Node(9);
obj.root.right.left.right = new Node(-1);
obj.root.right.right.right = new Node(9);
//Test Process
obj.delete_all_nodes();
}
}``````

#### Output

`````` Tree Element
10 6 2 9 8 7 -1 2 9
Delete Node : 10
Delete Node : 6
Delete Node : 8
Delete Node : 2
Delete Node : 7
Delete Node : 2
Delete Node : 9
Delete Node : -1
Delete Node : 9``````
``````// Swift 4 Program
// Delete entire nodes of a binary tree
// Using queue

//Binary Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
//Define Custom queue
class MyQueue
{
var element: Node? ;
var next: MyQueue? ;
init(_ element: Node? )
{
self.element = element;
self.next = nil;
}
}
class BinaryTree
{
var root: Node? ;
init()
{
//set initial tree root to null
self.root = nil;
}
//Recursive function
//Display preorder view of binary tree
func pre_order(_ node: Node? )
{
if (node != nil)
{
//Print node value
print(" ", node!.data, terminator: "");
self.pre_order(node!.left);
self.pre_order(node!.right);
}
}
//Remove a dequeue element
func dequeue(_ head: MyQueue? ) -> MyQueue?
{
{
//remove node
return temp;
}
return nil;
}
// Deleting all nodes in given tree in from top to bottom direction level by level
// Using queue
func delete_all_nodes()
{
if (self.root == nil)
{
print("\nEmpty Tree\n", terminator: "");
}
else
{
// Before delete, display tree elements
print("\n Tree Element \n", terminator: "");
self.pre_order(self.root);
//Make MyQueue variables
//initial tail is same to head of queue
//Get first node of tree
var auxiliary: Node? = self.root;
self.root = nil;
//iterate the MyQueue elements
{
//Get current head element of MyQueue
if (auxiliary!.left != nil)
{
tail!.next = MyQueue(auxiliary!.left);
tail = tail!.next;
}
if (auxiliary!.right != nil)
{
tail!.next = MyQueue(auxiliary!.right);
tail = tail!.next;
}
auxiliary!.left = nil;
//Remove element of MyQueue
print("\n Delete Node : ", auxiliary!.data, terminator: "");
//Deleted tree element
auxiliary!.left = nil;
auxiliary!.right = nil;
auxiliary = nil;
}
tail = nil;
}
}
}
func main()
{
//Make object
let obj: BinaryTree = BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
6     8
/     / \
2     7   2
/       \   \
9        -1   9
*/
obj.root = Node(10);
obj.root!.left = Node(6);
obj.root!.left!.left = Node(2);
obj.root!.right = Node(8);
obj.root!.right!.right = Node(2);
obj.root!.right!.left = Node(7);
obj.root!.left!.left!.left = Node(9);
obj.root!.right!.left!.right = Node(-1);
obj.root!.right!.right!.right = Node(9);
//Test Process
obj.delete_all_nodes();
}
main();``````

#### Output

`````` Tree Element
10  6  2  9  8  7  -1  2  9
Delete Node :  10
Delete Node :  6
Delete Node :  8
Delete Node :  2
Delete Node :  7
Delete Node :  2
Delete Node :  9
Delete Node :  -1
Delete Node :  9``````

## Output Explanation

The code implements the algorithm and deletes all nodes of the given binary tree in a level-order manner. It constructs the binary tree, performs the deletion, and prints the deleted nodes' values.

## Time Complexity

The time complexity of this algorithm depends on the number of nodes in the binary tree. If there are N nodes in the tree, the time complexity is O(N) as each node is processed once. The space complexity is also O(N) due to the queue used for traversal.

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