destroying a binary tree iteratively in java

Question

The task is commonly done during recursive post order traversal, and there are few examples online. One of them is here, but I wonder if it's correct because it seems that the _deleteTree() method only does a BFS and does no operation to nodes, and the deletion is done by simply set the root of the tree to null. It will no doubt return an empty tree. But is it the correct way to remove references to all the tree nodes?

Also, for iterative post order traversal, say, like below

public TreeNode postorderTraversal(TreeNode root) {
    if(root==null) return null;
    Stack<TreeNode> stack1=new Stack<>();
    Stack<TreeNode> stack2=new Stack<>();
    TreeNode cur=root;
    stack1.push(cur);
    while(!stack1.isEmpty()){
        cur=stack1.pop();

        if(cur!=null){
            stack2.push(cur);
        }

        if(cur.left!=null){
            stack1.push(cur.left);
        }
        if(cur.right!=null){
            stack1.push(cur.right);
        }
    }

    while(!stack2.isEmpty()){
        //elements poped will be in post order sequence
        }
    return root;
}

How to destroy a binary tree iteratively? Can someone give a sample code (java)?Thanks!

The code you linked to is misleading. It looks like someone has taken the C++ example and tried to rewrite it "word for word" in Java. The `deleteTree` concept simply doesn't apply to Java. The Java version of the method, as you pointed out, doesn't actually do anything. — Sam, Dec 30 '16 at 15:38

score 0 · Answer 1 · answered Dec 30 '16 at 17:12

Usually when you assign a node to null you technically get rid of all data. As with a linked list when you break its connection by setting its "next" per say to null you delete the list and java garbage collector takes care of the rest. So in the Java code you linked they are doing the same thing once the root is determined to have no children.

score 0 · Accepted Answer · answered Dec 30 '16 at 21:09

There's a better solution, which uses the tree nodes themselves to store the queue. Something like this:

static void clear(Node root) {
    while (root != null) {
        Node left = root.left;
        if (left == null) {
            Node right = root.right;
            root.right = null;
            root = right;
        } else {
            // Rotate the left child up.
            root.left = left.right;
            left.right = root;
            root = left;
        }
    }
}

destroying a binary tree iteratively in java

2 Answers2