How to recursively traverse a tree and create a list of visited nodes in python

Question

I have defined a class Tree which consists of a list of TreeNodes as below:

class Tree(object):
    def __init__(self, name, nodes):
        self.name = name
        self.nodes = nodes

class TreeNode(object):
    def __init__(self, name, parent):
        self.name = name
        self.parent = parent

As you can see, for each TreeNode I only define a single parent node. However, I want to write a Tree method that gives me a list of all parent nodes of a target node called targetNodeName (the output list should also include targetNodeName itself). For this, I have written a recursive function that iterates until a node with no parent is found (i.e. the root node) while building a list called results.

def allParents(self, targetNodeName, results):
    currentNode = next((node for node in self.nodes if node.name == targetNodeName))
    results.append(currentNode.name)
    if (currentNode.parent == None):
        print results
        return results
    else:
        return results.append(self.allParents(currentNode.parent, results))

However my recursive function does not perform as intended. I give an example where I first define a three-level, 7-node tree and then call the allParents method to get all parent nodes of node 'N7' i.e. ['N7', 'N3', 'N1'].

# create nodes
myTreeNodes = []
myTreeNodes.append(TreeNode(name = 'N1', parent = None))
myTreeNodes.append(TreeNode(name = 'N2', parent = 'N1'))
myTreeNodes.append(TreeNode(name = 'N3', parent = 'N1'))
myTreeNodes.append(TreeNode(name = 'N4', parent = 'N2'))
myTreeNodes.append(TreeNode(name = 'N5', parent = 'N2'))
myTreeNodes.append(TreeNode(name = 'N6', parent = 'N3'))
myTreeNodes.append(TreeNode(name = 'N7', parent = 'N3'))

myTree = Tree(name = 'ST1', nodes = myTreeNodes)

a = myTree.allParents(targetNodeName = 'N7', results = [])
print a

> ['N7', 'N3', 'N1']
> None

Although it prints out the correct list of parent nodes -note the 'debug' print command in the function- (i.e. ['N7', 'N3', 'N1']), the function returns None, meaning that i am dropped off the function with nothing to return. How can I fix this?

Gennady Kandaurov Gennady Kandaurov · Accepted Answer · 2016-11-22T19:55:49

Use is for checking if the value equals None or not. The allParents method can be simplified as following:

def allParents(self, targetNodeName):
    currentNode = next(node for node in self.nodes
                       if node.name == targetNodeName)
    if currentNode.parent is None:
        return [currentNode.name]
    else:
        return [currentNode.name] + self.allParents(currentNode.parent)

How to recursively traverse a tree and create a list of visited nodes in python

2 Answers