StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFixing pointers in binary tree delete function (node with 2 children)
text
Body
copied!<p>I'm a having a little trouble thinking how the hell do I fix the appropriate pointers when trying to delete a node from a binary tree where that node has 2 children.</p> <p>I understand the basic concept and I'm basically just having trouble fixing the pointers...</p> <p>So, basically, my delete function is mostly done and every case is already working (as far as my extensive testing go, everything worked OK), I'm only missing the case node with 2 children. Let's say we are inside the <code>else if</code> that deals with that case:</p> <p>I will have 2 pointers there, <code>currPtr</code> which holds the node to be deleted, <code>prevPtr</code> which holds the parent node. I also have a variable named <code>fromLeft</code> which defines if the <code>currPtr</code> parent comes from the left or right pointer on <code>prevPtr</code>. Then, I have a call to another function named <code>extractMin(Tree *t)</code> which extracts the lowest value in the tree. If I call this function with <code>currPtr->right</code> as argument, the successor of <code>currPtr</code> is going to be extracted from the tree (the function will deleted it from tree, fix the pointers and return the node pointer). The successor pointer is going to be saved on <code>tempPtr</code>.</p> <p>Here's the structure of my tree: </p> <pre><code>typedef int TreeElement; typedef struct sTree { TreeElement item; struct sTree *left; struct sTree *right; } Tree; </code></pre> <p>And the code for the extract function:</p> <pre><code>Tree *extractMin(Tree *tree) { Tree *prevPtr = NULL; Tree *currPtr = tree; while(currPtr->left) { prevPtr = currPtr; currPtr = currPtr->left; } if(prevPtr) prevPtr->left = currPtr->right; // inorder successor return currPtr; } </code></pre> <p>The code above is missing the case here the tree only has one node, the root node, it won't work properly and it also doesn't check if the tree has any nodes at all but, it works when a tree has a few nodes.</p> <p>So, how do I fix the necessary pointers on the <code>else if</code> for the node deletion? Also, remember that the <code>left</code> and <code>right</code> pointers on the tree nodes will always be pointing somewhere or be <code>NULL</code>.</p> <p>By the way, I want to do this iterative.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload