Monday, April 23, 2018

Delete a tree and free its nodes

Implementation of deletion of tree and its nodes is largely language dependent. If program is implemented using C/C++, it is program's duty to free up memory so code needs to traverse the tree in postorder fashion and keep freeing the nodes after visiting them.
If the program is implemented in Java, Java itself takes care of freeing up memory as long as object has no hard references pointing to it. Here is the Java solution for deleting a binary tree.

Java Solution:

public class DeleteTree {

    public static void main(String[] args) {
        //Build Tree        
        Node node1= new Node(1);
        Node node2= new Node(2);
        Node node3= new Node(3);
        Node node4= new Node(4);
        Node node5= new Node(5);
        Node node6= new Node(6);
        Node node7= new Node(7);
        Node node8= new Node(8);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node4.left = node8;
        node5.left = node6;
        node6.right = node7;

        deleteTree(node1);
    }


    private static Node deleteTree(Node root){
        if(root == null){
            return null;
        }

        deleteTree(root.left);
        deleteTree(root.right);
        System.out.println("Deleting node:" + root.data);
        root.left = null;
        root.right = null;
        root = null;
        return root;
    }

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data){
            this.data = data;
        }
    }
}

No comments:

Post a Comment

Categories