[c++ / pointers]: having objects A and B (B has vector member, which stores pointer to A), knowing A is it possible to retrieve pointer to B?

Question

Hello,

While trying to learn c++, I tried to implement class representing very basic trie. I came up with the following:

class Trie {
public:
    char data;
    vector<Trie* > children;

    Trie(char data);
    Trie* addChild(Trie* ch);    // adds child node

    (skipped others members/methods)

};

Method addChild checks if child ch with the same data is present in vector children, if not then it inserts it there, if yes - returns pointer to already existing child.

Now, considering this code snippet:

Trie t('c');
Trie* firstchild = new Trie('b');
Trie* secondchild = new Trie('a');


firstchild->addChild(secondchild);
t.addChild(firstchild);

if I only have pointer to secondchild, is it possible to somehow return pointers to firstchild or maybe even t?

I would like to know if it possible to do so, because the logic of my working code needs to traverse the trie "up" (from lower nodes to upper ones), to the parent of current object. Currently I am just using recursive function to travel down - but I am wondering if there exists any other way?

I am sorry if above is unclear or if I messed up somewhere, I am rather inexperienced and writing from my memory, without the working code.

Answer 1

The Trie object does not keep track of parent object. Its basically similar to single linked list and you can not traverse back unless you "know" the parent.

class Trie {
public:
    char data;
    vector<Trie* > children;
    Trie* parent;

    Trie(char data):parent(NULL){}
    Trie* addChild(Trie* ch)
    { //set the parent
     ch->parent = this;
    }

    (skipped others members/methods)

};

Then traverse would look something like:

traverse(Trie* pPtr)
{
Trie* currentPtr = pPtr;
 while(currentPtr)
 {
  currentPtr = currentPtr->parent;
 }

}

Answer 2

I only have pointer to secondchild, is it possible to somehow return pointers to firstchild or maybe even t?

No. You have to establish that relationship your self by passing the firstChild as a parent of the second child.

Answer 3

You need to add something like

Trie* parent;

or

Trie* previoussibling;
Trie* nextsibling;

to the class to get directly from firstchild to secondchild or vice-versa, or to go up from one of the children to t.

Note that if you need this kind of relationship then you will require more maintenance when adding and removing nodes to keep all the links correct.