13.1 Data Types |

For PBSTs we reuse TBST table and traverser structures. In fact, the
only data type that needs revision is the node structure. We take the
basic form of a node and add a member *pbst_parent* to point to its
parent node:

488. <PBST node structure 488> = /* A binary search tree with parent pointers node. */structpbst_node

{structpbst_node*pbst_link[2]; /* Subtrees. */structpbst_node*pbst_parent; /* Parent. */void*pbst_data; /* Pointer to data. */ };

This code is included in 486.

There is one special case: what should be the value of *pbst_parent*
for a node that has no parent, that is, in the tree's root? There are
two reasonable choices.

First, *pbst_parent* could be `NULL` in the root. This makes it easy
to check whether a node is the tree's root. On the other hand, we
often follow a parent pointer in order to change the link down from
the parent, and `NULL` as the root node's *pbst_parent* requires a
special case.

We can eliminate this special case if the root's *pbst_parent* is the
tree's pseudo-root node, that is, (**struct** **pbst_node** *) &*tree*->*pbst_root*. The downside of this choice is that it becomes
uglier, and perhaps slower, to check whether a node is the tree's
root, because a comparison must be made against a non-constant
expression instead of simply `NULL`.

In this book, we make the former choice, so *pbst_parent* is `NULL`
in the tree's root node.

**See also:**
[Cormen 1990], section 11.4.