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.