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.

Parent Node
Child 1
Child 2

remove nodes binary tree — Fig 2: Delete all nodes

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

delete left subtree — Fig 3: left subtree

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:

delete complete binary tree — Fig 4: delete complete tree

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