How an object can be treated as an array and iterates through it and save the response in javascript with trie data structure?

Question

I am a beginner in the data structure. I have just started learning it. I am trying to create a family structure using the trie data structure. I am referring to the document for that on github here: https://gist.github.com/tpae/72e1c54471e88b689f85ad2b3940a8f0#file-trie-js-L44

This is some code.

function TrieNode(key) {
  // the "key" value will be the character in sequence
  this.key = key;
  
  // we keep a reference to parent
  this.parent = null;
  
  // we have hash of children
  this.children = {};
  
  // check to see if the node is at the end
  this.end = false;
}

// -----------------------------------------

// we implement Trie with just a simple root with null value.
function Trie() {
  this.root = new TrieNode(null);
}

// inserts a word into the trie.
// time complexity: O(k), k = word length
Trie.prototype.insert = function(word) {
  var node = this.root; // we start at the root 
  
  // for every character in the word
  for(var i = 0; i < word.length; i++) {
    // check to see if character node exists in children.
    if (!node.children[word[i]]) {
      // if it doesn't exist, we then create it.
      node.children[word[i]] = new TrieNode(word[i]);
      
      // we also assign the parent to the child node.
      node.children[word[i]].parent = node;
    }
    
    // proceed to the next depth in the trie.
    node = node.children[word[i]];
    
    // finally, we check to see if it's the last word.
    if (i == word.length-1) {
      // if it is, we set the end flag to true.
      node.end = true;
    }
  }
};

My doubt is while inserting the node, how we are iterating through word and creating a node as:

 node.children[word[i]]

which is not understandable to me. Also how key, parent, children are declared in function TrieNode? Are they treated as global variables which are initialized whenever an object is created? And why root has been declared in other functions and how does it work? P.S. I have to insert the tree like this:

var familyHead = {
      name: 'Chit',
      gender:'Male',
      grandfather:'',
      grandmother:'',
      father:'Shan',
      mother:'Anga',
      wife:'Amba',
    children : [
    {
      name: 'Chit',
      gender:'Male',
      grandfather:'',
      grandmother:'',
      father:'Shan',
      mother:'Anga',
      wife:'Amba',
      children :[]
}]

} ... continue

Answer 1

You can give JavaScript objects properties that refer to the related objects accomplish what you want to form a graph. (Do not use a trie, that's for something else.).

For example, create a plain JavaScript object for each person.

// Create an to represent each unique person
const chit = { name: 'Chit', gender: 'male' };
const shan = { name: 'Shan', gender: 'male' };
const anga = { name: 'Anga', gender: 'female' };
const anba = { name: 'Anba', gender: 'female' };

// Give them properties that establish the relationships as required
chit.father = shan;
chit.mother = anga;
chit.wife = amba;
/// ...

These are uni-directional links so far. If you also want the father to have an array of their children, then you'll have to maintain this data structure as you build it. You'll want to have some convenience functions for doing this.

To establish a parent-child relationship between two people minimally one thing must happen:

1. The child object should have its parent property set to the parent object.

If, as a matter of convenience or efficiency, you also want to maintain a cache of the list of children each person has then furthermore:

2. The parent object should have the child object added to its children array.

Doing so overspecifies the parent-child relationship and so the data structure must maintain integrity. This means that you'll want to provide functions to make modifications to the tree while checking for inconsistencies. For example, it may not make sense to simultaneously try to establish two parent-child relationships for the same child, or to have a child with no parent (someone will need to have no parent because you can't store an infinitely deep generational history), or to have a person listed as a child but not also simultaneously have that same child listed as having the same parent.

In such a function, one might now go so far as to check the whole tree for integrity, but it may be sufficient to just check the parts of the structure being modified.

When establishing a new parent-child relationship, check to see if the child already has a parent. There are two strategies for dealing with this if they do, depending on whether it makes sense to edit the otherwise biologically immutable property of who is one's parent (for example, consider a process like adoption)

1. Throw an exception.
2. Edit the relationship by removing the child from the parent's array of children before updating to set the new parent.

Here I will provide an implementation that permits one parent of each gender. I'll map the gender of the parent to either mother or father property names just to illustrate the convenience of doing so. If you find you need to represent families with two mothers, for example, then you will need to make use an array of parents instead. (But your example uses mother and father, and so shall I.)

const parent_property_name = {
  male: 'father',
  female: 'mother'
};

function establishParentChildRelationship(parent, child) {
   if (!child.parent) child.parent = {};
   if (child[parent_property_name[parent.gender]]) throw new Error('child already has a parent of that gender');
   child[parent_property_name[parent.gender]] = parent;
   if (!parent.children) parent.children = [];
   parent.children.push(child);
}

Hopefully you can see that because of the upkeep required that it is not typically done to further store explicit grandfather and grandmother relationships in the tree. The father of a father is implicitly the grandfather and can be determined as such. Similarly the siblings of a parent are aunts and uncles, etc. Cousins and second cousins can all be determined based on just the parent-child relationships. There's no need to explicitly store it again. Furthermore one must consider whether or not you need to explicitly define mother and father because they may come from parent + gender. (or is it fine not to represent concepts like female-father? The details of these things will likely be defined by the legal framework in which you are working. But the world is a complex place.)

The marital relationships (legal or religious or otherwise), however, do require additional links. One must also consider whether the data structure is to permit plural marriage (which may require an array, much like children) and same-gender marriage ('married' + 'gender' => 'husband' or 'wife'). But for monogamous marriages, one could imagine, minimally, just representing this with maritalPartner.

function establishMonogamousMaritalPartnerRelationship(person1, person2) {
   if (person1.maritalPartner || person2.maritalPartner) throw new Error('already married!');
   person1.maritalPartner = person2;
   person2.maritalPartner = person1;

You could also use the trick of mapping gender to husband or wife as necessary. Or if you want to represent plural marriage, then you could use an array of partners (much like was done with children.)

The data structure may need to be modified again to be able to represent the complexities of these relationships changing over time. (For example divorce or 2nd marriage, adoption, emancipation, gender transition or reassignment, etc.)

---

Let me also take a moment to clarify what the trie is for. (It is not applicable to the family tree.)

The trie represents words as a tree, where each node is a letter and each node's parent node is the letter that came before it. A complete word is marked with a flag on the node in the tree that is that words final letter.

Consider a trie storing the words be, bee, bell, and ball:

.
└── b
    ├── a
    │   └── l
    │       └── l*
    └── e*
        ├── e*
        └── l
            └── l*

Nodes marked with a * represent complete words (with the end flag in your example). Note that a word may end even if more letters are permitted to follow it to form a different work. (e.g.: be is a word, even though it may be followed by e or l). Every node with an end flag, represents a word determined by its ancestry in the tree.

---

Finally, let me quickly address your question about the nature of how key, parent, and children are declared in function TrieNode.

What you are looking at is a JavaScript constructor. I suggest you read the basics Or this answer.

But in this specific case, calling new TrieNode('X') will create a JavaScript object that looks basically like this:

{ key: 'X', parent: null, children: {}, end: false }