Instead of externally keeping a list you can build it as you go.
def list_parentals(tree, element, parents):
this, children = tree
new_parents = [this] + parents
if this == element:
return new_parents
else:
for child in children:
x = list_parentals(child, element, new_parents)
# If x is not None, return it
if x:
return x
list_parentals(t, 'George', [])
# ['George', 'Fanny', 'Eric', 'Alan']
Hello, an independent learner here. After struggling with some Leetcode problems on tree recursion in python, I'm wondering about resources for getting better at it. Any book or website recommendations? For example, I plugged a few users' solutions into the 'visualize python' website to try to understand the process better, but I'm still not getting it. In the recursion stack, values can be passed around ('up' and 'down' the tree?) . Just want to understand this better. I did the first couple chapters of SICP a while back--maybe I should go back to that unless someone knows of other good material as well. Thanks.
Instead of externally keeping a list you can build it as you go.
def list_parentals(tree, element, parents):
this, children = tree
new_parents = [this] + parents
if this == element:
return new_parents
else:
for child in children:
x = list_parentals(child, element, new_parents)
# If x is not None, return it
if x:
return x
list_parentals(t, 'George', [])
# ['George', 'Fanny', 'Eric', 'Alan']
For "my recursive function returns None", that is a very, very classical problem. You'll find hundred of detailed answers about that on SO searching these words.
But in short, a recursive function must return something always, not just when it found something. Typically, on such an example, you must return a result when you found the correct leaf. But if you don't want that result to be lost, then, you must also return something when you call that recursion that found the leaf. And when you call that recursion that called that recursion that found the leaf.
Keep in mind that what you get as a final result is the return value of the first call to list_parentals. If that first call doesn't return anything, then, it doesn't matter that some recursive subcalls did.
Secondly, the way to build such a path is precisely to take advantage of the recursion. Trying to create a list in a global variable when you find a matching leaf is not easy. And you may end up trying to compute that with a iterative algorithm, when the whole point of recursion is to do that for you.
Here is a working recursive method (I tried to keep it as close are your own code as possible)
tree=('Alan', [('Bob', [('Chris', []), ('Debbie', [('Cindy', [])])]), ('Eric', [('Dan', []), ('Fanny', [('George', [])])]), ('Hannah', [])])
def list_parentals(tree, element):
if tree[0] == element:
return [element]
else:
for child in tree[1]:
sub=list_parentals(child, element)
if sub:
return [tree[0]] + sub
return []
r=list_parentals(tree, 'George')
print(f"{r=}")
The logic of that is that list_parental(tree, 'George') returns the path in tree to leaf 'George', or [] (or None, or False, doesn't matter) if no such leaf is found.
So (just think of it as a mathematical expression, not as code, for now), list_parental(('Alan', [('Bob', [('Chris', []), ('Debbie', [('Cindy', [])])]), ('Eric', [('Dan', []), ('Fanny', [('George', [])])]), ('Hannah', [])]), 'George') is just Alan plus `list_parental(('Eric', [('Dan', []), ('Fanny', [('George', [])])]), 'George').
``list_parental(('Eric', [('Dan', []), ('Fanny', [('George', [])])]), 'George')is justEricpluslist_parental(('Fanny', [('George', [])]), 'George')`.
list_parental(('Fanny', [('George', [])]), 'George') is just Fanny plus list_parental(('George', []), 'George').
list_parental(('George', []), 'George') is just George.
To keep this consistent, all returns must be lists.
Hence my code.
list_parental(tree, leafName) is [leafName] is the root of the tree match leafName.
Else
list_parental(tree, leafName) is [tree[0]] + list_parental(child, leafName) if one of the child contains leafName, that is if list_parental(child, leafName) is not empty.
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}]]
def processNode(bp, space=''):
if ('name' in bp[0].keys() ):
print( space + bp[0]['name'])
if ('subNodesTitle' in bp[0].keys()):
print( bp[0]['subNodesTitle'])
processNode( bp[0]['subNodes'],space=space+' ')
if (len(bp) > 1):
processNode( bp[1:],space=space )
processNode(root)
This function can recurse through an unbalanced tree,
