When to use parent pointers in trees?

Question

There are many problems in which we need to find the parents or ancestors of a node in a tree repeatedly. So, in those scenarios, instead of finding the parent node at run-time, a less complicated approach seems to be using parent pointers. This is time efficient but increase space. Can anyone suggest, in which kind of problems or scenarios, it is advisable to use parent pointers in a tree?

For example - distance between two nodes of a tree?

Answer 1

using parent pointers. This is time efficient but increase space.

A classic trade-off in Computer Science.

In which kind of problems or scenarios, it is advisable to use parent pointers in a tree?

In cases where finding the parents in runtime would cost much more than having pointers to the parents.

Now, one has to understand what cost means. You mentioned the trade-off yourself: One should think whether or not is worth to spend some extra memory to store the pointers, in order speedup your program.

Answer 2

Here are some of the scenarios that I can think of, where having a parent pointer saved in a node could help improve out time complexity

-> Ancestors of a given node in a binary tree
-> Union Find Algorithm
-> Maintain collection of disjoint sets
-> Merge two sets together

Now according to me in general having a parent pointer for any kind of tree problem or trie problem would make your traversal up-down or bottom-up easier.

Hope this helps!