Shall I store a parent pointer in a tree/graph node?

Question

I am developing a tree/graph like data structure. It should be more like a directed acyclic graph. One of the requirements is to find the path from root to a specific node, which means when user pick a node, the path from the root would be highlighted.

So, the question is shall I store a parent pointer in each node? Or a more general question would be when should I store a parent pointer in each node? What are the advantages and disadvantages?

Thanks in advance!

ps. parent pointer == a pointer to the parent node.

Answer 1

Generally, you store a pointer back to the parent only if you are going to be using algorithms that require it. Otherwise, it is unnecessary overhead both in terms of the memory used to store the pointer and the extra complexity of updating those pointers when you insert a node or rebalance/reorganize the tree.

The typical algorithms used with trees (breadth-first and depth-first search and traversal) don't require parent pointers, which is why your average run-of-the-mill tree implementations generally don't include them.

Your "highlight path from the root" requirement might make parent pointers useful, although there are other ways to implement that. In general, one should avoid putting redundant information into data structures until it is proven that they are necessary for performance reasons.

Answer 2

If it will be possible to change (extend) this structure in future (and for most of code it is possible), I would suggest to postpone adding this link until it will be clearly needed.

It's much simpler to add something than to remove when code is in use...

But it's still useful to have several potential extensions in mind when designing data structures...

Answer 3

To elaborate on Kristopher Johnson's reply: "you should only keep a pointer to the parent of you need it".

Remember that for many algorithms that traverse a tree/graph, during the traversal, you are traveling from the parent to the child, so you actually have the parent pointer in hand. You can use this parent pointer (for example passing it to a recursive function) instead of paying the costs of keeping it in your structure.

Another point: for general graphs this question is the same as "should I store the in-edges (in addition to the out-edges) in my nodes?". If you look at the boost graph library, you will find a template library that allows you this choice at compile time.

Answer 4

The overhead of storing a parent pointer is relative to how often you update the tree/graph, and how many nodes are in it. The overhead of not storing a parent pointer for some algorithms depends on how often they're run. I can't tell you how often you update the map or how often you need a parent pointer, but my advice would be to implement both and run a profiler, or make some kind of logical decision based on which operations take more time.