Delete all nodes of a binary tree in java (recursive/ DFS/ example)

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

1. Parent Node
2. Child 1
3. Child 2

Algorithm used to delete all nodes of binary tree is as follows:

1. Go to parent node
2. Delete left child node
3. Delete right child Node
4. 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