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
delete binary tree
Fig 1: Delete binary tree – 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
remove nodes binary tree
Fig 2: Delete all nodes

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

Download Code – Delete nodes binary tree DFS

 

Scroll to Top