[C] Indirect/Double Pointer Technique ("Triple Ref")
Intuition\nDelete nodes in post-order traversal so we don\'t dangle pointers. As well, use an indirect pointer so we don\'t have to worry about as many edge cas
# Intuition\nDelete nodes in post-order traversal so we don\'t dangle pointers. As well, use an indirect pointer so we don\'t have to worry about as many edge cases when modifying left/right references. This approach takes inspiration from:\n\n- the Computerphile video "**Triple Ref Pointers**"\n- the article "**Linus Torvalds\' linked list argument for good taste, explained**" (for some reason my posts get taken down when I share links, so do Google these).\n\n# Approach\n\n## Post-Order Traversal\nWe can\'t delete a node, and then delete its child\'s nodes. This results in dangling pointers. Instead, we\'ll need to keep recursing post-order so that the first deletions are the last ones. Then, and only then, we\'ll process the earlier deletions. When deleting a node, we can therefore assume that `result` will have the necessary references for the children if they are deleted. We just add the children, then `NULL` out the node.\n\n## Indirect Pointers\nEach reference to a node is often passed to an implementation\'s DFS function by value. This causes issues when you pass a `struct TreeNode *`, but actually want to change what is pointing to the `struct TreeNode **`. This usually comes in the form of passing `node->next` to the function, which passes the address (let\'s say `0xDEADBEEF`) by value, however, we oftentimes will need to change `node->next`, so even though we pass `0xDEADBEEF`, we want to change _what would be read back from where it is originally written_.\n\nIt is commonplace (especially at my university) that C has "pass by reference": no it doesn\'t. You pass addresses by value. The same applies for Python and Java, causing issues with editing references like in this question, though in those languages\' cases, a "sentinel" or "dummy" pointer is used to simulate passing by reference. To see solutions far more elegant than mine, look at the C++ posts here, which do have pass by reference in the form of the `&` operator (I am very jealous).\n\nThis solution will therefore pass pointers to pointers to `struct TreeNode` in order to not only pass the node, but in its enclosing memory address so we can change `node->next` without dealing with return values.\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$a\\ lot$$\n\n# Code\n```\nvoid delete_nodes(\n    struct TreeNode **tree,\n    struct TreeNode **result,\n    int *resultSize,\n    bool *should_delete\n) {\n    // Guard clause to do nothing on NULL node\n    if (!*tree) return;\n\n    // Keep recursing post-order so that the latest deletions process first.\n    // That way, we don\'t dangle any of our TreeNode references.\n    delete_nodes(&(*tree)->left, result, resultSize, should_delete);\n    delete_nodes(&(*tree)->right, result, resultSize, should_delete);\n\n    // Here we process the deletion, though if this node isn\'t getting deleted we bail.\n    if (should_delete[(*tree)->val] == false) return;\n\n    // When a node is deleted, its children become new forest roots. We\'ll therefore have to\n    // push each child (if existent) to the result array.\n    if ((*tree)->left) result[(*resultSize)++] = (*tree)->left;\n    if ((*tree)->right) result[(*resultSize)++] = (*tree)->right;\n\n    // The reason why we use double/indirect pointers is so that we can overwrite the reference\n    // pointing to the tree being deleted, instead of having to mangle return values and deal\n    // with even more edge cases regarding leaves and roots.\n    *tree = NULL;\n}\n\nstruct TreeNode **delNodes(struct TreeNode *root, int *to_delete, int to_deleteSize, int *returnSize)\n{\n    // Initialize output variables\n    *returnSize = 0;\n    struct TreeNode **result = calloc(1001, sizeof(struct TreeNode *));\n\n    // Create should_delete map\n    bool *should_delete = calloc(1001, sizeof(bool));\n    for (int i = 0; i < to_deleteSize; i++) {\n        should_delete[to_delete[i]] = true;\n    }\n\n    // Post-order traversal; re-add root if it survives\n    delete_nodes(&root, result, returnSize, should_delete);\n    if (root) result[(*returnSize)++] = root;\n    return result;\n}\n```
['C']