Binary tree recursive delete

Question

I am trying to understand how a recursive method to delete a binary search tree works. The code that I found in many places looks like this:

void destroy_tree(struct node *leaf) { if( leaf != 0 ) { destroy_tree(leaf->left); destroy_tree(leaf->right); free( leaf ); } } 

I cannot understand, a) how does it work if there is no return in the routine? b) when is free () called? I think of, for example, a tree like this:

  10 / \ 6 14 / \ / \ 5 8 11 18 

So, I understand that I cross 10-> 6-> 5, and then I call destroy_tree (5-> left). Therefore, the sheet inside if is NULL, and what depends on if is not executed, so 5 is not deleted. Where can I make mistakes in this reasoning? How does winding and unwinding work? Any help is kindly appreciated :-)

Answer 1

It looks like at this moment:

 void destroy_tree(struct node *leaf_5) { if( leaf_5 != 0 ) // it not { destroy_tree(leaf_5->left); // it NULL so the call does nothing destroy_tree(leaf_5->right); // it NULL so the call does nothing free( leaf_5 ); // free here } } 

Nothing is required to return ... the "history" of steps is in the call stack, which looks something like this:

 destroy_tree(leaf_10) destroy_tree(leaf_10->left, which is leaf_6) destroy_tree(leaf_6->left, which is leaf_5) 

So, after leaf_5 leaves, it goes back on the stack and does destroy_tree(leaf_6->right, which is leaf_8) ... etc.

Answer 2

This is how the function works:

 void destroy_tree(struct node *leaf) { if( leaf_5 != 0 ) // it not { destroy_tree(leaf->left); // Traverse the tree all the way left before any of the code below gets executed. destroy_tree(leaf->right); // Traverse the tree all the way right from the final left node before any of //the code below gets executed free( leaf ); // Free the final node } } 

Below is the code of how the full implementation of recursive deletion should look:

 void DeleteNode(TreeNode*& tree); void Delete(TreeNode*& tree, ItemType item); void TreeType::DeleteItem(ItemType item) // Calls the recursive function Delete to delete item from tree. { Delete(root, item); } void Delete(TreeNode*& tree, ItemType item) // Deletes item from tree. // Post: item is not in tree. { if (item < tree->info) Delete(tree->left, item); // Look in left subtree. else if (item > tree->info) Delete(tree->right, item); // Look in right subtree. else DeleteNode(tree); // Node found; call DeleteNode. } void GetPredecessor(TreeNode* tree, ItemType& data); void DeleteNode(TreeNode*& tree) // Deletes the node pointed to by tree. // Post: The user data in the node pointed to by tree is no // longer in the tree. If tree is a leaf node or has only one // non-NULL child pointer, the node pointed to by tree is // deleted; otherwise, the user data is replaced by its // logical predecessor and the predecessor node is deleted. { ItemType data; TreeNode* tempPtr; tempPtr = tree; if (tree->left == NULL) { tree = tree->right; delete tempPtr; } else if (tree->right == NULL) { tree = tree->left; delete tempPtr; } else { GetPredecessor(tree->left, data); tree->info = data; Delete(tree->left, data); // Delete predecessor node. } } void GetPredecessor(TreeNode* tree, ItemType& data) // Sets data to the info member of the rightmost node in tree. { while (tree->right != NULL) tree = tree->right; data = tree->info; }