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!

Answer 1

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;
        }
    }
}

Answer 2

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.