Binary tree node keeping reference to its parent

Question

Is it 'traditional' (or 'ethical') for a Node in a binary tree to keep a reference to its parents?

Normally, I would not think so, simply because a tree is a directed graph, and so the fact that the PARENT-->CHILD link is defined should not mean that CHILD --->PARENT is also defined. In other words, by keeping a reference to the parent, we would somehow break the semantic of the tree.

But I would like to know what people think?

I asked because I was given a problem of finding the lowest common parent of two given nodes in a tree. If each node has a reference to its parent, the problem would be super easy to solve, but that feels like cheating!

Thanks

Answer 1

How you implement a binary tree should be dependent on your needs.

If your application requires tree traversal in the direction of leaf to trunk, then the best way to do so would be to implement references to parent nodes.

I find that it is better to fit your data structures to your needs rather than try to make workarounds with other logic. After all, why must a tree be a directed graph? Making it directed is a specific implementation, much like a list and its specific implementation as a singly- or doubly-linked list.