What are the advantages of binary search trees with parent pointers?

Question

Up until this point, I've been implementing Binary Search Trees with left and right pointers, like:

template<typename T>
struct BSTNode{
    BSTNode* left;
    BSTNode* right;
    T data;
}

I came across implementations where nodes also had pointers to the parent node. Why would you want to do that? And what are the trade-offs?

Answer 1

From one point of view your question is valid because the parent pointer introduces a redundancy into the structure which is avoidable in several situations. But in case of binary trees this gives you the huge benefit that you can jump "up" one level (i.e. from a node to its parent) without remembering the parent node's address. Several algorithms (for example, getting the number of nodes between to two values) can be implemented very effectively and simple if the parent node of a node is known.

The trade-off is the redundancy: if you modify the structure of the tree (for example by balancing the tree) you must remember to update both the left/right and the parent pointers to keep the consistency of the tree.

Answer 2

Binary search tree refers to quite a general class of binary trees. For the binary search tree there is no reason to have a parent pointer.

There are more specialized variants of binary trees, however, where the parent pointer is beneficial. Look for AVL trees or red black trees for example. These specializations impose further restrictions on the tree's layout to achieve various goals, such as guaranteed O(log n) complexity for lookup/insert/removal in a red black tree by ensuring the tree is always balanced.

To fulfill these restrictions, the parent pointer comes in handy sometimes. Of course it does so by trading memory (the pointer) for speed (looking up the parent by algorithm).

Consider your favourite book on data structures to see how and why, or wikipedia.