I'm trying to make a function in Python, that takes an arbitrary node of a tree, and populates a list of lists based on the node give.
Given the following badly drawn tree:
If we start at, for example, node 5, we should get:
And the nodes should end up in a list of lists, one list for each depth.
The nodes in python:
nodes = [
{'id': 1, 'parent': None},
{'id': 2, 'parent': 1},
{'id': 3, 'parent': 1},
{'id': 4, 'parent': 2},
{'id': 5, 'parent': 2},
{'id': 6, 'parent': 5},
{'id': 7, 'parent': 6},
{'id': 8, 'parent': 3}
]
We can only see parents, not children, but this is the data format I have to work with, sadly.
So from this, if we take node 5, we want to end up with a node list looking something like this:
nl = [
[{'id': 6, 'parent': 5}],
[{'id': 4, 'parent': 2}, {'id': 5, 'parent': 2}],
[{'id': 2, 'parent': 1}, {'id': 3, 'parent': 1}],
]
This is the code I have so far. I figure a recursive function is probably the simplest way. Unfortunately it seems to do nothing like what I think it should, and obviously I'm doing something very wrong. And this code doesn't even consider geting the child nodes which I'm not entirely sure how to deal with at all, apart from possibly handing the afterwards which would be much easier.
node_list = []
def pop_list(nodes=None, parent=None, node_list=None):
if parent is None:
return node_list
node_list.append([])
for node in nodes:
if node['parent'] == parent:
node_list[-1].append(node)
if node['id'] == parent:
parent = node['parent']
return pop_list(nodes, parent, node_list)
print pop_list(nodes, 5, node_list)
Here is the output:
[[], [{'id': 3, 'parent': 1}], []]
Not exactly sure where I'm going wrong here.
A recursion tree is useful for visualizing what happens when a recurrence is iterated. It diagrams the tree of recursive calls and the amount of work done at each call. For instance, consider the recurrence. T(n) = 2T(n/2) + n2.
A tree is recursive data type.
Steps to solve recurrence relation using recursion tree method: Draw a recursive tree for given recurrence relation. Calculate the cost at each level and count the total no of levels in the recursion tree. Count the total number of nodes in the last level and calculate the cost of the last level.
Following is an example of a recursive function to find the factorial of an integer. Factorial of a number is the product of all the integers from 1 to that number. For example, the factorial of 6 (denoted as 6!) is 1*2*3*4*5*6 = 720 .
The problem is here
if node['id'] == parent:
parent = node['parent']
The current parent
will be overwritten by its parent.
Moreover, you should add return node_list
at the end of the function, or use node_list
as results.
def pop_list(nodes=None, parent=None, node_list=None):
if parent is None:
return node_list
node_list.append([])
for node in nodes:
if node['parent'] == parent:
node_list[-1].append(node)
if node['id'] == parent:
next_parent = node['parent']
pop_list(nodes, next_parent, node_list)
return node_list
>>> print pop_list(nodes, 5, node_list)
[[{'id': 6, 'parent': 5}], [{'id': 4, 'parent': 2}, {'id': 5, 'parent': 2}], [{'id': 2, 'parent': 1}, {'id': 3, 'parent': 1}]]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With