- Given a binary tree, we would like to delete all nodes of binary tree using recursive algorithm.
- To delete a binary tree, we will use postOrder traversal of depth first search (dfs) algorithm.
- To delete any node, first we need to delete its children.
- We have already discussed delete a given node from binary search tree (BST) using DFS
Examples: delete all nodes of binary tree using java
Example 1: Delete binary tree shown in Fig 2.
Delete all nodes of a binary tree shown in Fig 2. Binary tree has 3 nodes i.e.
- Parent Node
- Child 1
- Child 2
Algorithm used to delete all nodes of binary tree is as follows:
- Go to parent node
- Delete left child node
- Delete right child Node
- Delete Current Node i.e. current parent node.
Example 2: Delete all nodes of a binary tree using java.
Delete all nodes of binary tree shown in Fig 3:
- Apply Example 1 algorithm to left subtree of Node A (Fig 1).
- Delete Node D & Node E
- Delete Node B & all nodes of subtree will be deleted (Fig 3).
Example 3: Delete all nodes of a binary tree using java.
Delete all nodes of binary tree shown in Fig 1. We have demonstrated the deletion process in Fig 3 as follows:
- Perform postOrder traversal of binary tree.
- Delete left subtree of current node.
- Delete right subtree of current node.
- Delete current node.
- Refer Fig 4 for deletion order of nodes, in a binary tree.
Time complexity of algorithm is O(n).
Program: delete all nodes of binary tree using recursive algorithm in java
1.) DeleteTree Class:
- DeleteTree class deletes all nodes of a binary tree.
- We will traverse the binary tree using depth first search recursive algorithm.
package org.learn.Question; public class DeleteTree { public static Node deleteTree(Node root) { if(null == root) { return null; } root.left = deleteTree(root.left); root.right = deleteTree(root.right); root = null; return root; } }
2.) Node Class:
- Node class representing the nodes of a binary tree
package org.learn.Question; public class Node { public int data; public Node left; public Node right; public Node(int num) { this.data = num; this.left = null; this.right = null; } public Node() { this.left = null; this.right = null; } public static Node createNode(int number) { return new Node(number); } }
3.) App Class:
- We are constructing the binary tree in main method.
- We will call method of deleteTree class, to delete all nodes of a binary tree.
package org.learn.Client; import org.learn.Question.DeleteTree; import org.learn.Question.Node; public class App { public static void main( String[] args ) { // root level 0 Node A = Node.createNode(60); // Level 1 Node B = Node.createNode(20); Node C = Node.createNode(80); // Level 2 Node D = Node.createNode(10); Node E = Node.createNode(30); Node F = Node.createNode(70); Node G = Node.createNode(90); // Level 3 Node H = Node.createNode(65); Node I = Node.createNode(75); Node J = Node.createNode(85); Node K = Node.createNode(95); // connect Level 0 and 1 A.left = B; A.right = C; // connect level 1 and level 2 B.left = D; B.right = E; C.left = F; C.right = G; // connect level 2 and level 3 F.left = H; F.right = I; G.left = J; G.right = K; Node node = DeleteTree.deleteTree(A); if(null == node) { System.out.println("Binary tree deleted successfully"); } else { System.out.println("Error: Could not delete tree successfully"); } } }
Output: delete all nodes of binary tree using recursive algorithm (java)
Binary tree deleted successfully
Download Code – Delete nodes binary tree DFS