Postorder traversal using recursion in Python

Question

I am a new to python programming and recently I have experienced some problems in programming recursions.Consider I have a Graph as : a)list of vertices b) and an adjacency list (as a 2 dimensional list) and I am trying to get an lists which will give me the Postorder traversal order of these vertices(Post_Order_List_of_Node), an inverse of this which will tell the order of any node(Order_of_Node) and a list of father of all nodes. I have written the following piece of code:

My "order" variable is global but according to output, its not getting incremented.

I dont know why but the variable "order" isnt getting updated.

def Post_Order(node,order,father):
    Order_of_Node = [No_of_Nodes]*No_of_Nodes   #Initialization
    Post_Order_List_of_Node = [No_of_Nodes]*No_of_Nodes     #Initialization
    def recursive(node,order,father):
        if len(Spanning_Tree[node]) == 0:
            Order_of_Node[node] = order
            Post_Order_List_of_Node[order] = node
            order = order + 1
            Father_List[node] = father
            del(Spanning_Tree[father][0])
            return
        else:
            while(len(Spanning_Tree[node])!=0): 
            recurse(Spanning_Tree[node][0],order,node)
    recurse(node,order,father)
    return Post_Order_List_of_Node,Order_of_Node
Father_List = [0]*No_of_Nodes
root = 0
father = 0
order = 1
Order = []
Order = Post_Order(root,order,father)

Answer 1

order is not getting updated because, unlike what you claim, it is not a global variable. By defining your recursive function like this,

def recursive(node,order,father):

any reference to order within the scope of that function will only modify the parameter, not the global variable. Within that function, you only modify order in the if branch, but use it in the else branch. So the update to the parameter never gets passed on.

In order to use order as a global variable, declare it as such:

def recursive(node, father):
    global order
    if ...

---

Another issue in your code - when you set values for Post_Order_List_of_Node, you use

Post_Order_List_of_Node[order] = node

However, order starts at 1 instead of at 0, so for the last node you'll get an error. You need to use

Post_Order_List_of_Node[order-1] = node

instead.

---

One inefficiency that you may or may not have noticed is in how you process nodes:

def recursive(node,father):
    if len(Spanning_Tree[node]) == 0:
        # Process node
    else:
        while(len(Spanning_Tree[node])!=0): 
            # Process child

In one call to recursive, you only process the children or the node itself. Your code works because of the while loop - you call recursive twice for each child that has children itself. Instead of doing it that way, you could switch it to do this:

def recursive(node,father):
    for child in Spanning_Tree[node]:
        # process child
    # process node

This has the added advantage that it does not require modifying Spanning_Tree. However, it does require that you either make sure that you do have a tree (no cycles) or that you mark nodes as visited before you start processing any children.