I was wondering if it's possible to delete a binary tree with O(1) additional memory, without using recursion or stacks.

I have managed to write the naive, recursive postorder traversal solution (which uses stack memory):

void deleteTreeRec(Node *root)
{
   if (root == NULL) return;
   deleteTreeRec(root->left);
   deleteTreeRec(root->right);
   cout << "Deleting node " << root->data << endl;
   delete root;
}

I've heard that this can be achieved using (inorder) Morris traversal, which seems wrong, or at least counterintuitive, given the fact that tree deletion requires, as far as I understand, traversal in a postorder fashion (start by deleting the two subtrees, and only afterwards, the root). However, I haven't found any detailed description/pseudocode of the solution, hence I am trying my luck here.

If anybody could shed some light on this issue, it would be greatly appreciated. Thanks!

CodePudding user response：

During the deletion the existing nodes of the binary tree can be used as a singly linked list: The nodes always using the left "link" is seen as the linked list.

To delete all nodes you simply repeat the following steps:

1. find the tail of the "linked list"
2. if right is non-null, move it to the end of the "list"
3. store the pointer the next element in the "list" in a temporary
4. replace the old head with the temporaty and repeat if the "list" is non-empty

Starting the search for the new tail at the previous tail results in the algorithm running in O(n) where n is the number of nodes in the binary tree.

void deleteTree(Node* root)
{
    Node* tail = root;
    while (root != nullptr)
    {
        // update tail
        while (tail->left != nullptr)
        {
            tail = tail->left;
        }

        // move right to the end of the "list"
        // needs to happen before retrieving next, since the node may only have a right subtree
        tail->left = root->right;

        // need to retrieve the data about the next
        Node* next = root->left;

        delete root;

        root = next;
    }
}