1

I am trying to solve a interview question: how to convert a BST to a double linked list. Below is my code. I am really confused about how python recursion works. Why after the convert2DoubleLst_recursive , the prev and head remain to be None, I have assigned a new value to these two variables, why after this method call, I cannot save the change. I remembered that python pass arguments by reference, but why here I cannot save the changes. Many thanks in advance.

def convert2_recursive(node):
    prev,head=None,None
    convert2DoubleLst_recursive(node,prev,head)
    end=head.lChild
    printList(head,end)

def convert2DoubleLst_recursive(node,prev,head):
    if node:
        convert2DoubleLst_recursive(node.lChild,prev,head)
        node.lChild=prev
        if prev:
           prev.rChild=node
        else:
           head=node
        nextNode=node.rChild
        head.lChild=node
        node.rChild=head
        prev=node
        convert2DoubleLst_recursive(nextNode,prev,head)
lexie
  • 79
  • 1
  • 8
  • 1
    Please fix your indentation - this code, as it is, won't compile. – BartoszKP Jan 17 '14 at 14:50
  • 3
    "I remembered that python pass arguments by reference" You remembered incorrectly. (I recommend reading http://stackoverflow.com/a/986145/110707 ) – Wooble Jan 17 '14 at 14:51
  • I guess you could emulate pass by reference like behaviour by passing the two parameters wrapped in a list or dictionary. But you shouldn't. – tobias_k Jan 17 '14 at 15:02
  • Python is pass-by-value, where all values are references to objects. There's no way to change what object someone else's variable points to. – kindall Jan 17 '14 at 15:43

1 Answers1

1

Naively put, because there is no pass-by-reference in Python. Recursion is not your problem.

It may become a little clearer, when you think "There are no variables in Python, only names and values".

When the statement convert2DoubleLst_recursive(node.lChild, prev, head) is executed, actually the function convert2DoubleLst_recursive is called with the values that node.lChild, prev and head point to at that time.

Then, within convert2DoubleLst_recursive, those values are given the (local) names node, etc. (which are different names from those before!).

Later you assign new values to those names, recurse (which is not actually relevant in your code) and essentially Python forgets the names and their values when exiting the function.

Basically, between line 8 and 10 prev does not change it's value (as you experienced), because the name used in the caller is never seen inside of the callee. The value assigned to that name is not changed in line 3 and it is not relevant what happens inside the callee.

If you want to pass values back to your caller, you have to return them.

Alternatively you could replace None by a guardian object that behaves like your node class and represents None.

Usually, though, there are better data structures you would use in Python than linked lists. (Python lists for example are already linked lists internally and can be used instead.)

A much deeper analysis can be found here: https://stackoverflow.com/a/986145/110707 .

Community
  • 1
  • 1