We have discussed recursive implementation to deleteĀ an entire binary tree here.
We strongly recommend you to minimize your browser and try this yourself first.
Now how to delete an entire tree without using recursion. This could easily be done with the help of Level Order Tree Traversal. The idea isĀ for each dequeued node from the queue, delete it after queuing its left and right nodes (if any). The solution will work as we are traverse all the nodes of the tree level by level from top to bottom, and before deleting the parent node, we are storing its children into queue that will be deleted later.
Ā
Ā
C++
/* Non-Recursive Program to delete an entire binary tree. */#include <bits/stdc++.h> using namespace std; Ā Ā // A Binary Tree Node struct Node { Ā Ā Ā Ā int data; Ā Ā Ā Ā struct Node *left, *right; }; Ā Ā /* Non-recursive function to delete an entire binary tree. */void _deleteTree(Node *root) { Ā Ā Ā Ā // Base Case Ā Ā Ā Ā if (root == NULL) Ā Ā Ā Ā Ā Ā Ā Ā return; Ā Ā Ā Ā Ā Ā // Create an empty queue for level order traversal Ā Ā Ā Ā queue<Node *> q; Ā Ā Ā Ā Ā Ā // Do level order traversal starting from root Ā Ā Ā Ā q.push(root); Ā Ā Ā Ā while (!q.empty()) Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Node *node = q.front(); Ā Ā Ā Ā Ā Ā Ā Ā q.pop(); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (node->left != NULL) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.push(node->left); Ā Ā Ā Ā Ā Ā Ā Ā if (node->right != NULL) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.push(node->right); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā free(node); Ā Ā Ā Ā } } Ā Ā /* Deletes a tree and sets the root as NULL */void deleteTree(Node** node_ref) { Ā Ā _deleteTree(*node_ref); Ā Ā *node_ref = NULL; } Ā Ā // Utility function to create a new tree Node Node* newNode(int data) { Ā Ā Ā Ā Node *temp = new Node; Ā Ā Ā Ā temp->data = data; Ā Ā Ā Ā temp->left = temp->right = NULL; Ā Ā Ā Ā Ā Ā return temp; } Ā Ā // Driver program to test above functions int main() { Ā Ā Ā Ā // create a binary tree Ā Ā Ā Ā Node *root =Ā newNode(15); Ā Ā Ā Ā root->left = newNode(10); Ā Ā Ā Ā root->right = newNode(20); Ā Ā Ā Ā root->left->left = newNode(8); Ā Ā Ā Ā root->left->right = newNode(12); Ā Ā Ā Ā root->right->left = newNode(16); Ā Ā Ā Ā root->right->right = newNode(25); Ā Ā Ā Ā Ā Ā //delete entire binary tree Ā Ā Ā Ā deleteTree(&root); Ā Ā Ā Ā Ā Ā return 0; } |
Java
/* Non-recursive program to delete the entire binary tree */import java.util.*; Ā Ā // A binary tree node class NodeĀ { Ā Ā Ā Ā int data; Ā Ā Ā Ā Node left, right; Ā Ā Ā Ā Ā Ā public Node(int data)Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā this.data = data; Ā Ā Ā Ā Ā Ā Ā Ā left = right = null; Ā Ā Ā Ā } } Ā Ā class BinaryTreeĀ { Ā Ā Ā Ā Node root; Ā Ā Ā Ā Ā Ā /* Non-recursive function to delete an entire binary tree. */Ā Ā Ā Ā void _deleteTree()Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā // Base Case Ā Ā Ā Ā Ā Ā Ā Ā if (root == null) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return; Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Create an empty queue for level order traversal Ā Ā Ā Ā Ā Ā Ā Ā Queue<Node> q = new LinkedList<Node>(); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Do level order traversal starting from root Ā Ā Ā Ā Ā Ā Ā Ā q.add(root); Ā Ā Ā Ā Ā Ā Ā Ā while (!q.isEmpty())Ā Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Node node = q.peek(); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.poll(); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (node.left != null) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.add(node.left); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (node.right != null) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.add(node.right); Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā /* Deletes a tree and sets the root as NULL */Ā Ā Ā Ā void deleteTree()Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā _deleteTree(); Ā Ā Ā Ā Ā Ā Ā Ā root = null; Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā // Driver program to test above functions Ā Ā Ā Ā public static void main(String[] args)Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā // create a binary tree Ā Ā Ā Ā Ā Ā Ā Ā BinaryTree tree = new BinaryTree(); Ā Ā Ā Ā Ā Ā Ā Ā tree.root = new Node(15); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.left = new Node(10); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.right = new Node(20); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.left.left = new Node(8); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.left.right = new Node(12); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.right.left = new Node(16); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.right.right = new Node(25); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // delete entire binary tree Ā Ā Ā Ā Ā Ā Ā Ā tree.deleteTree(); Ā Ā Ā Ā } } Ā Ā // This code has been contributed by Mayank Jaiswal(mayank_24) |
Python3
# Python program to delete an entire binary tree # using non-recursive approach Ā Ā # A binary tree node class Node: Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # A constructor to create a new node Ā Ā Ā Ā def __init__(self, data): Ā Ā Ā Ā Ā Ā Ā Ā self.data = dataĀ Ā Ā Ā Ā Ā Ā Ā Ā self.left = NoneĀ Ā Ā Ā Ā Ā Ā Ā self.right = NoneĀ Ā # Non-recursive function to delete an entrie binary tree def _deleteTree(root): Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Base Case Ā Ā Ā Ā if root is None: Ā Ā Ā Ā Ā Ā Ā Ā returnĀ Ā Ā Ā Ā Ā Ā # Create a empty queue for level order traversal Ā Ā Ā Ā q = [] Ā Ā Ā Ā Ā Ā # Do level order traversal starting from root Ā Ā Ā Ā q.append(root) Ā Ā Ā Ā while(len(q)>0): Ā Ā Ā Ā Ā Ā Ā Ā node = q.pop(0) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if node.left is not None: Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.append(node.left) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if node.right is not None: Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.append(node.right) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā node = NoneĀ Ā Ā Ā return node Ā Ā # Deletes a tree and sets the root as None def deleteTree(node_ref): Ā Ā Ā Ā node_ref = _deleteTree(node_ref) Ā Ā Ā Ā return node_ref Ā Ā # Driver program to test above function Ā Ā # Create a binary tree root = Node(15) root.left = Node(10) root.right = Node(20) root.left.left = Node(8) root.left.right = Node(12) root.right.left = Node(16) root.right.right = Node(25) Ā Ā # delete entire binary tree root = deleteTree(root) Ā Ā Ā Ā # This program is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
/* Non-recursive program to delete the entire binary tree */using System; using System.Collections.Generic; Ā Ā // A binary tree node public class NodeĀ { Ā Ā Ā Ā public int data; Ā Ā Ā Ā public Node left, right; Ā Ā Ā Ā Ā Ā public Node(int data)Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā this.data = data; Ā Ā Ā Ā Ā Ā Ā Ā left = right = null; Ā Ā Ā Ā } } Ā Ā public class BinaryTreeĀ { Ā Ā Ā Ā Node root; Ā Ā Ā Ā Ā Ā /* Non-recursive function to Ā Ā Ā Ā delete an entire binary tree. */Ā Ā Ā Ā void _deleteTree()Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā // Base Case Ā Ā Ā Ā Ā Ā Ā Ā if (root == null) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return; Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Create an empty queue for level order traversal Ā Ā Ā Ā Ā Ā Ā Ā Queue<Node> q = new Queue<Node>(); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Do level order traversal starting from root Ā Ā Ā Ā Ā Ā Ā Ā q.Enqueue(root); Ā Ā Ā Ā Ā Ā Ā Ā while (q.Count != 0)Ā Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Node node = q.Peek(); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.Dequeue(); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (node.left != null) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.Enqueue(node.left); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (node.right != null) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.Enqueue(node.right); Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā /* Deletes a tree and sets the root as NULL */Ā Ā Ā Ā void deleteTree()Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā _deleteTree(); Ā Ā Ā Ā Ā Ā Ā Ā root = null; Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā // Driver program to test above functions Ā Ā Ā Ā public static void Main(String[] args)Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā // create a binary tree Ā Ā Ā Ā Ā Ā Ā Ā BinaryTree tree = new BinaryTree(); Ā Ā Ā Ā Ā Ā Ā Ā tree.root = new Node(15); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.left = new Node(10); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.right = new Node(20); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.left.left = new Node(8); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.left.right = new Node(12); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.right.left = new Node(16); Ā Ā Ā Ā Ā Ā Ā Ā tree.root.right.right = new Node(25); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // delete entire binary tree Ā Ā Ā Ā Ā Ā Ā Ā tree.deleteTree(); Ā Ā Ā Ā } } Ā Ā // This code has been contributed by 29AjayKumar |
Javascript
<script> /* Non-recursive program to delete the entire binary tree */Ā Ā // A binary tree node class NodeĀ { Ā Ā Ā Ā constructor(data) Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā this.data = data; Ā Ā Ā Ā Ā Ā Ā Ā this.left = this.right = null; Ā Ā Ā Ā } } Ā Ā let root; Ā Ā /* Non-recursive function to delete an entire binary tree. */function _deleteTree()Ā { Ā Ā Ā Ā // Base Case Ā Ā Ā Ā Ā Ā Ā Ā if (root == null) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return; Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Create an empty queue for level order traversal Ā Ā Ā Ā Ā Ā Ā Ā let q = []; Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Do level order traversal starting from root Ā Ā Ā Ā Ā Ā Ā Ā q.push(root); Ā Ā Ā Ā Ā Ā Ā Ā while (q.length != 0)Ā Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā let node = q.shift(); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (node.left != null) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.push(node.left); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (node.right != null) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.push(node.right); Ā Ā Ā Ā Ā Ā Ā Ā } } Ā Ā Ā Ā Ā Ā /* Deletes a tree and sets the root as NULL */function deleteTree()Ā { Ā Ā Ā Ā _deleteTree(); Ā Ā Ā Ā Ā Ā Ā Ā root = null; } Ā Ā // Driver program to test above functions root = new Node(15); root.left = new Node(10); root.right = new Node(20); root.left.left = new Node(8); root.left.right = new Node(12); root.right.left = new Node(16); root.right.right = new Node(25); Ā Ā // delete entire binary tree deleteTree(); Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // This code is contributed by rag2127 </script> |
Time Complexity: O(n)
As it is a normal level order traversal and we are visiting every node just once.
Auxiliary Space: O(b)
Here b is the breadth of the tree or the maximum number of elements at any level. The extra space is required to store the elements of a level in the queue.
This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Ā
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
