Solving the tree problem on Fams.ng

Ademola Onasoga

Cover Image for Solving the tree problem on Fams.ng

Ademola Onasoga

April 5, 2025

Problem definition

We are building a family social application, where people would come online to discover and have a social connection with their kinsmen like a friend would do on Facebook - just that this is for family.

To create a differentiation from Facebook, there is a need to have features that are unique to this social media platform not present in the rest - and one of that feature is a family tree. A page to see how each family members are related at a glance.

In Building the family tree, we are starting with an ancestral tree - to see the children of the ancestor.

The problem is on how to structure this data, the ancestor tree, in such a way that it can be easily accessed and updated with the recursive nested data at least n(0).

Another problem is that MongoDB, the database we are using, do not support updates on deeply nested recursive data.

Data structure

{
  ancestor: id,
  children:  [
     { member: id,  children: [
       {member: id, children: []},
     ] },
     { member: id,  children: [] }
  ]
}

Data representation model

This is a data representation model of the data using D3 collapsible tree.

Tree Screenshot

The real problem: Putting a new member on the tree. You might have to look for a parent and then update. The problem is, the parent can be in the 4th generation. You would have had to search all the people in the first 3 generations no matter how many they are to find it there.

How do you find, update and retrieve optimally?

Proposed solutions

Change the database, use one that supports deeply nested recursive data updates (up to the 6th nested child)
- Use alternative databases:
  - PostgreSQL
  - Graph database
    - Neo4j
Fetch the whole family tree, use JavaScript to find the nested child and update it
- Drawback: Slow latency as server is used to perform potentially expensive operations
Use GraphQL to reduce roundtrips and traverse data more efficiently
Use a different data structure to save and retrieve data

In-depth exploration of the solutions

Solving it using first principles, independent of implementation or tech stack

Saving the Family Tree

Method 1

Saving:
- Save the parent first
- Attach the ID of the child to the parent #### Method 1: Relational Tree with Parent-Child References
Saving:
- Save the parent first
- Save the child
- Attach the ID of the child to the parent's children array
  Example:
```
children: [23, 234, 1]
```
Reading:
- Get the parent node
- Get the children using their IDs
- To get the next generation, recursively fetch each child’s children

Pseudocode:

GET node
GET node.children
// Example
root = [23, 234, 1]
response = [{}, {}, {}]
then fetch each children recursively

pseudo code: - Examples json GET node, Get node.children, ...

root

[ 23, 234, 1 ], response: [{}, {}, {}]. then get each children of each` For every generation, there is nth of children round trip e.g, to get the second generation, that's 3 round trip, and the third would be n* number of children.

Pros

Good for writes as it is on first scope => first parent

Cons

Bad for reading the entire family tree

Method 2: PostgreSQL Migration

Saving

Same as method 1

Method 3: Graph Database (Neo4j)

Use a graph database like Neo4j for better relationship handling.

Method 4: GraphQL Integration

Use GraphQL to traverse the data for method 1 or method 2.

Blog.