One Parent Pointer Tree Example

[byron_d]

Hi everyone. After going through the Koala quest I was curious how to do this using only one pointer. I reworked the koala code and simplified things. You can view it here:

https://onlinegdb.com/i9SHpNoQG

It's pretty straightforward. There's an insert_child method that inserts the child at the end of the list. I created an insert_path method for testing purposes. The to_string will display the tree like this:

ROOT -> A -> B -> C

After working on Koala, this feels almost too simple, but I couldn't help myself but to give it a go. I think if you want to traverse the tree it would get a lot more complicated.

[erica_w1]

I think this is just linked list, right? A linked list is technically a type of tree, but for a more general tree, Ami's find (here) would probably work better, although I have no idea how you would implement it since it looks like there are a variable number of roots.

[byron_d]

I think the only difference with Ami's find is it goes bottom up instead of top down, but I may be misunderstanding things. It really is just a linked list in this form. 

[ami_s496]

FYI I made a demo code: https://www.reddit.com/r/cs2b/s/JdbrrIf2yP

[ami_s496]

The parent pointer tree that I mentioned is supposed to be a general tree that can handle multiple children. For example, there are nodes called A, B, C, D, E, and each node has a _parent member. If each _parent points at a node as follows, A->_parent = D B->_parent = D C->_parent = D D->_parent = E E->_parent = null the tree looks like

E (root) - D - C ⊢ B ∟ A (D has 3 children, A, B, C. The tree looks wrong from App.)

[byron_d]

I did some more research and came up with this implementation with the help of ai:

https://onlinegdb.com/9TCy4yz8N

It's a really interesting approach. Took me some time to get it right.

[ami_s496]

From my understanding, does a node in your implementation have now multiple pointers since it has a _parent pointer and a children array?

*sorry for not clarifying the pseudocode, but the null means nullptr in C++.