Objective: Given a binary tree, write an algorithm to delete it.
This is one of the basic problem in trees. if you are new to trees then this problem will help you build your foundation.
Approach:
- To delete a binary tree, we need to set all the node objects to null then garbage collection will take care of rest of the things. If you are writing the code in C/C++ then you will have to clear the allocated memory by yourself.
- Do the post order traversal and set the node to null.
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class DeleteTree { | |
// to delete a binary tree, we need to set all the node objects to null then | |
// garbage collection will take care of rest of the things | |
//do the post order traversal and set the node to null | |
public static Node deleteTree(Node root) { | |
if (root != null) { | |
deleteTree(root.left); | |
deleteTree(root.right); | |
System.out.println("Deleting Node:" + root.data); | |
root=null; | |
return root; | |
} | |
return null; | |
} | |
public static void main(String[] args) { | |
Node root = new Node(1); | |
root.left = new Node(2); | |
root.right = new Node(3); | |
root.left.left = new Node(4); | |
root.left.right = new Node(5); | |
deleteTree(root); | |
} | |
} | |
class Node { | |
int data; | |
Node left; | |
Node right; | |
public Node(int data) { | |
this.data = data; | |
} | |
} |
Output: Deleting Node:4 Deleting Node:5 Deleting Node:2 Deleting Node:3 Deleting Node:1