" heap-use-after-free" error even when I am not accessing the deleted node of a binary tree

Question

I was trying to generate the inorder traversal of a binary tree using O(1) space ie I don't wanna use recursion or any other data structures such as queues or vectors to store the node.

Edit: This runtime error occurs on Leetcode but does not occur if I run the same code in vscode or any other online compiler.

So if you wanna debug this example just paste the code below in the inorderTraversal function in the question and add the custom testcase provided below.

Minimal Reproducible example for the code:

Testcase: Binary Tree = [1,2] 
ie root is 1 and 2 is the left child of 1

vector<int> inorderTraversal(TreeNode* root) {

        TreeNode* tmp = root;
        delete tmp;
        cout<<"returning"<<endl;
        return{};
}

This code generates the same error, Code runs till the cout statement despite throwing the runtime error listed below but does not return the empty vector.

On LeetCode I get this error:

Line 77: Char 9:
=================================================================
==23==ERROR: AddressSanitizer: heap-use-after-free on address 0x503000000078 at pc 0x56254f388795 bp 0x7ffc48e817b0 sp 0x7ffc48e817a8
READ of size 8 at 0x503000000078 thread T0

This is my solution where I process the node in inorder and then delete the processed node, I am making sure that the de-allocated node is never accessed again but still the solution gives this error:

On commenting out the delete tmp line the solution works fine but still I want to know why this error pops up even if I'm not accessing the node that is deleted. As whenever a node is deleted, it's parent node's left or write pointer is replaced with the children of the deleted node.

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>inorder;
      
        while(root){
            TreeNode* curr = root;
            TreeNode* prev = NULL;
            bool isLeft = true;
        
            while(curr){
                cout<<curr->val<<endl;
                if(curr->left){
                    prev = curr;
                    curr = curr->left;
                    isLeft = true;

                }
                else{
                    inorder.push_back(curr->val);
                    TreeNode* tmp = curr;

                    if(prev){
                        if(isLeft)prev->left = curr->right;
                        else prev->right = curr->right;
                    }
                    else{
                        root=curr->right;
                    }
                    curr = curr->right;
                    delete tmp;
                }
            }
        }
        return inorder;
    }
};

I was trying to generate inorder traversal of a binary tree while using O(1) and deleted the processed node one by one and replaced their links but got heap use after free error.

Answer 1

The problem is that the caller of your function (in this case the LeetCode platform code) still has a reference to root, and wants to properly free the memory it had allocated for the tree. It does not expect that you would have freed that memory. This is not the task of your function.

So when it starts to free up the memory it had allocated for the tree, it will run into that error (or some other undefined behaviour), because it accesses the memory referenced by root in order to visit every dependent node of the tree and free it.

An important principle here is that the responsibility of freeing memory lies solely with the code that had allocated it. Since your function did not allocate it, it should not free it either.