8.5.6 Finding the Parent of a Node |

The last component of *tavl_delete*() left undiscussed is the
implementation of its helper function *find_parent*(), which requires
an algorithm for finding the parent of an arbitrary node in a TAVL
tree. If there were no efficient algorithm for this purpose, we would
have to keep a stack of parent nodes as we did for unthreaded AVL
trees. (This is still an option, as shown in
Exercise 3.) We are fortunate that such an algorithm
does exist. Let's discover it.

Because child pointers always lead downward in a BST, the only way
that we're going to get from one node to another one above it is by
following a thread. Almost directly from our definition of threads,
we know that if a node *q* has a right child *p*, then there is a left
thread in the subtree rooted at *p* that points back to *q*. Because
a left thread points from a node to its predecessor, this left thread
to *q* must come from *q*'s successor, which we'll call *s*. The
situation looks like this:

This leads immediately to an algorithm to find *q* given *p*, if *p*
is *q*'s right child. We simply follow left links starting at *p*
until we we reach a thread, then we follow that thread. On the other
hand, it doesn't help if *p* is *q*'s left child, but there's an
analogous situation with *q*'s predecessor in that case.

Will this algorithm work for any node in a TBST? It won't work for the root node, because no thread points above the root (see Exercise 2). It will work for any other node, because any node other than the root has its successor or predecessor as its parent.

Here is the actual code, which finds and returns the parent of *node*.
It traverses both the left and right subtrees of *node* at once, using
*x* to move down to the left and *y* to move down to the right. When
it hits a thread on one side, it checks whether it leads to *node*'s
parent. If it does, then we're done. If it doesn't, then we continue
traversing along the other side, which is guaranteed to lead to
*node*'s parent.

327. <Find parent of a TBST node 327> = /* Returns the parent ofnodewithintree, or a pointer totbst_rootifsis the root of the tree. */staticstructtbst_node*find_parent(structtbst_table*tree,structtbst_node*node)

{if(node!=tree->tbst_root)

{structtbst_node*x, *y;for(x=y=node; ;x=x->tbst_link[0],y=y->tbst_link[1])if(y->tbst_tag[1] ==TBST_THREAD)

{structtbst_node*p=y->tbst_link[1];if(p==NULL||p->tbst_link[0] !=node)

{while(x->tbst_tag[0] ==TBST_CHILD)x=x->tbst_link[0];p=x->tbst_link[0]; }returnp; }elseif(x->tbst_tag[0] ==TBST_THREAD)

{structtbst_node*p=x->tbst_link[0];if(p==NULL||p->tbst_link[1] !=node)

{while(y->tbst_tag[1] ==TBST_CHILD)y=y->tbst_link[1];p=y->tbst_link[1]; }returnp; } }else

return(structtbst_node*) &tree->tbst_root; }

This code is included in 311, 668, and 670.

**See also:**
[Knuth 1997], exercise 2.3.1-19.

**Exercises:**

***1.** Show that finding the parent of a given node using this algorithm,
averaged over all the node within a TBST, requires only a constant
number of links to be followed.
[answer]

**2.** The structure of threads in our TBSTs force finding the parent of the
root node to be special-cased. Suggest a modification to the tree
structure to avoid this.
[answer]

**3.** It can take several steps to find the parent of an arbitrary node in a
TBST, even though the operation is “efficient” in the sense of
Exercise 7.7-4. On the other hand, finding the parent of a
node is very fast with a stack, but it costs time to construct the
stack. Rewrite *tavl_delete*() to use a stack instead of the parent
node algorithm.
[answer]