CODEWITHSUNDEEP
pythonalgorithmrecursionstacktree-traversal
user3541631
user3541631

Reputation: 4008

Traverse a Spaghetti Stack and reverse to a tree

I have a Spaghetti Stack (an N-ary tree data structure in which child nodes have pointers to the parent nodes) - received from a database.

The "stack" received from database is just a list with all nodes so can be multiple stacks inside.

The Nodes are records from the database where parent.id is a ForeignKey to another record of the same type.

class Node_Category:
  def __init__(self, value):
    self.value = value
    parent_id = id

The structure is something like this:

Category 1
 -Category 1_1
  --Category 1_1_1
 -Category 1_2
Category_2
Category_3
 -Category 3_1
 -Category 3_2

What I need:

Now I know the child's parent. Starting from a parent Node I need to know his children.

So I need to traverse the 'Spaghetti Stack' add connections in parent nodes to children so I can traverse from parent to children.

A parent can have 0, one or multiple children.

Because I don't know the depth of the stack I tried to do it recursive.

Also I think a form of memorization is necessary because looping thru array a parent of a parent get multiple accesses.

What I tried:

   def _recurse_for_parents(self, category, path=None):

    if path is None:
        path = []
    path.append(category)
    if category.parent:
        return self._recurse_for_parents(category.parent, path)
    return path

 for record in categories:
            self._recurse_for_parents(category)

The issues:

In the loop I can hit the parent, first level child, second level etc:

Child1_L2-Child1_L1->parent; Child1_L1->parent; parent->Null
Child1_L1->parent; parent->Null
Child2_L1->parent; parent->Null

So, I'm hitting the same path on different depths multiple times. Also for each path I need to add the link from his parent back to children.

Upvotes: 1

Views: 623

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 133995

This seems pretty simple in concept. I don't see where a recursive implementation would be of particular use. An iterative solution is straightforward. I'll outline the basic idea.

I assume you are given an array of N nodes, and you have an ID for each node.

The first thing I'd do is create a dictionary, keyed by ID, and the values are a new node type that has the structure:

NewNode
    Id - the node's id
    Children - a list of some type that contains the ids of the node's children
    Whatever other data the database gives you.

For each node in the list, look up the parent in the dictionary, and add the node to the list of the parent's children.

While you're going through the list in the step above, you should run across one node that has no parent id. That's the root. If there is no such node or there's more than one, then you have invalid data.

Anyway, you look up that node's id in the dictionary and save it as the root.

Example

Let's say you have two trees:

           100                  200
         /     \             /   |   \
      101      120         201  210  220
       |      /   \         |         |
      102   121   122      202       221
     /   \               /  |  \
   103   110           203 204 205
    |
   104

So you have these nodes:

ID      Parent
104     103
103     102
102     101
101     100
100     NULL
110     102
121     120
120     100
122     120
203     202
202     201
201     200
204     202
205     202
210     200
221     220
220     200
200     NULL

What I'm suggesting is that you create a dictionary from that list, keyed by the node id. And with a children list for each node.

Now, starting with the first item in the list, you look up the parent, and add the node to the parent's child list. So for the first item, you see that node 104 has parent 103. You add a reference to node 104 to 103's child list.

Then you move on to the next node in the list. When you're done, your dictionary looks like this:

ID      Parent  Children
104     103     []
103     102     [104]
102     101     [103]
101     100     [102]
100     NULL    [101,110,120]
110     102     []
121     120     []
120     100     [121,122]
122     120     []
203     202     []
202     201     [203,204,205]
201     200     [202]
200     NULL    [201,210,220]
204     202     []
205     202     []
210     200     []
221     220     []
220     200     [221]

Your dictionary now contains the inverted trees. You can scan the dictionary, looking for nodes that have a Parent value of NULL. Those are the roots of your trees. Each root has an array of references to its child nodes, and those child nodes have references to their children, etc.

Upvotes: 5

m.raynal
m.raynal

Reputation: 3113

A simple solution could then be the following one, supposing your nodes are represented by integers, and your array is such that array[2] = 3 means 'the parent of node 2 is node 3'.. Let's call array the list (or any iterable) of all nodes, and then :

adjacencies = []
for node in tree : # iterate on all your nodes
    adjacencies += [(node.parent_id, node)]

And then to get the children of a given node you simply have to process as follows :

def get_children (parent :int, adjacencies :list) -> set:
    return {child for (parent, child) in adjacencies}

If you want a more precise solution, you'll need to give me more informations about your implementation ; then i'll edit.

Upvotes: 0

Related Questions