Should child nodes have a reference to their parents?

Question

Let's say you are engineering a chat room software.

let client = new Client();
let room = rooms.FindRoom();
room.addClient(client);

This room (parent) now has a client (child).

client.on('message', (event) => {
   // With the above code, room must be found
   let room = rooms.FindClientsRoom(client);
   if(room){
       room.handleMessage(event);
   }
});

Or we have a child that knows about its parent

let client = new Client();
let room = rooms.FindRoom();
room.addClient(client);
client.setRoom(room);


client.on('message', (event) => {
   let room = client.getRoom();
   if(room){
       room.handleMessage(event);
   }
});

This is incredibly fast compared to looking for a client within 1000s of rooms. But is there something wrong with the design pattern? In any system, such as XML, do child nodes know about their parents? Should they?

Answer 1

Your question is basically the same as "should linked list items have a reference to the previous item?", and the answer is the same: it depends. There are use cases when a singly-linked list is correct, and there are use cases when a doubly-linked list is correct.

The important point here is that it is the use case that matters, not the format: XML does not specify whether child nodes know about their parents, that is a matter of the design of the parser which reads the XML and creates in-memory data structures for it. Some parsers will do this, other ones won't.

If you need a quick lookup from your child nodes to the parent nodes, then put it in. If you don't, Keep It Simple S... and don't have them.

Answer 2

Personally, I think the first pattern you showed to be a mistake. As you pointed out, it takes a lot of time to find the room.

The general problem with the second pattern is that it makes reference counting garbage collection fail. (This issue varies by language.)

What you missed is that there is a third pattern. Specifically, that the events to the client can identify the room. This works well if the events are coming from the room. It doesn't work well if the events are from an unrelated external source.

You might also want to consider if a client can be associated with multiple rooms.

Answer 3

If you're doing this on a chat server application, then you should use a database. The most common database design for a tree is that parents do not have references to their children, only the child have foreign key reference to their parents. Instead, the parent to child relation should be handled by an index.

If you're doing this in a chat client application, then don't worry too much about it. Even the heaviest chat software users aren't going to have more than hundred room or so simultaneously, don't worry about performance and pick the simplest implementation that makes your life and future maintenance easy rather than worrying about negligible performance differences.

Answer 4

In most tree models you want to know the parent of nodes, you will likely have a use case for it. You already mentioned your own use case and keeping track of parents is cheap so it is a no-brainer.

In other tree applications you typically want the node to be able to tell you its path, and its level (or depth). For this you also need the parent. It is a common thing to take onboard for tree nodes.

Answer 5

In general terms, you're adding an edge connecting Client and Room.

If this is a real world example, this is a poor model to make it a parent-child relationship. As others have pointed out, you may have to extend it to multiple client-room relationships which breaks a single back-pointer from Child -> Room.

This may seem wildly unrealistic but, say someone has more than one chat window open - they are now in more than one room at a time.

Even if you were modeling physical presence, a booking system would have to cope with the person who books more than one room on behalf of others (common) or books a long slot for one room whilst in the middle having an overlapping short use of another.

In-memory you can model such edges as a hash key in a dictionary that is a combination of client + room ID. This would continue to be a fast lookup.

That approach also extends easily to databases adding such records with a composite key.

It has a secondary benefit that you can save these edge records over time, showing a history of the relationships.

Answer 6

Trees are used for a variety of purposes, some of which are facilitated by having child nodes hold parent pointers, and some of which would require that child nodes not have parent pointers.

If child nodes have references to their parents, than a reference to a child can effectively identify both a tree and location within it. On the other hand, making a snapshot of a tree's state will require making a copy of all the nodes therein.

If tree nodes are immutable, and modifications to a tree are performed by producing a modified tree node and replacing referencces to the original with references to the modified version, then code may take a snapshot of a tree merely by copying a reference to its current root node.

Each approach is excellent for some purposes, but will work poorly for some others. Depending upon what you're doing with trees, either approach may work better. Alternatively, it may be useful to use a hybrid approach in which every tree node object is either referenced by exactly one tree, or will never be modified. I can't think offhand of situations where it would be useful for non-shared nodes to have parent references, but they could do so.

Answer 7

A mentioned in other answers already; what to do depends on the requirements.

Add a link from the child back to the parent if you regularly and/or quickly need to be able to find the parent from the child. Don't add a link if there's no reason to, or if the cost of adding this link outweighs the benefit (e.g. additional resources used, additional code to write & maintain, more complexity in determining when garbage collection can occur).

Regarding how you go about implementing such a relationship though, I'd say it's important to have the logic defined in one place. i.e. If you've decided that a child should always reference its parent then don't use the following to set that relationship:

room.addClient(client);
client.setRoom(room);

Instead, have your addClient method perform the setRoom operation for you; so you don't have to remember to call the two methods together each time you need this operation to take place.

function addClient(Client client) {
    this.clients.Add(client);
    client.joinRoom(this);
}

... And have the same logic in place in any operations to remove the relationship:

function removeClient(Client client) {
    this.clients.Remove(client);
    client.leaveRoom(this);
}

Note: I've also used joinRoom instead of setRoom, and passed this to leaveRoom. Those allow you to easily change your client from being able to have a single parent to multiple, should you choose to switch your approach.

Answer 8

Adding new fields requires more memory. The difference between the first and second approach is more CPU vs more RAM usage. As they can be a tradeoff, need to decide which one to optimize depending on the application.