Python: passing parameters over functions

Question

Python Experts,

I have been trying to implement BST using Python and here is my code for the insert function:

Draft 1:

def insert(self, val):
    newNode = self._Node(val)

    if (self._root is None):
        self._root = newNode
    else:
        self._insert(self._root,val)

def _insert(self, node, val):

    if node is None:
        node = self._Node(val)

    elif val >= node._val:

        self._insert(node._right, val)
    else:
        self._insert(node._left, val)

But, I'm unable to construct the tree except the root. I'm guessing I messed up somewhere with the parameters passing over the two functions because when I modify the code as below, I get it alright:

Draft 2:

def insert(self, val):
    newNode = self._Node(val)

    if (self._root is None):
        self._root = newNode
    else:
        self._insert(self._root,val)

def _insert(self, node, val):

    if val >= node._val:
        if node._right is None:
                node._right = self._Node(val)
        else:
                self._insert(node._right, val)
    else:
        if node._left is None:
                node._left = self._Node(val)
        else:
                self._insert(node._left, val)

I'm trying hard to understand why the draft 2 works but draft 1 doesn't. Any help here? Thanks in advance!

I might have messed up the indentation while copying. Updated the intendation now! :) — Gowtham Ganesh
– Gowtham Ganesh, Commented Sep 20, 2016 at 23:32

juanpa.arrivillaga · Accepted Answer · 2016-09-20 23:41:52Z

The fundamental misunderstanding you have is how variable assignment works and interacts with Python's evaluation strategy: call-by-sharing.

Essentially, in your first draft, when you do the following:

def _insert(self, node, val):

    if node is None:
        node = self._Node(val)
    ...

You are simply assigning to the name (variable) node the value of self._Node(val) but then when you leave the scope, the new object is destroyed! Even though node used to refer to the value that was passed in by the method call, simple assignment doesn't mutate the object that is referenced by the name, rather, it reassigns the name.

In your second draft, however:

def _insert(self, node, val):

    if val >= node._val:
        if node._right is None:
            node._right = self._Node(val)
        else:
            self._insert(node._right, val)

You are mutating an object i.e.: `node._right = self._Node(val)

Here is a simple example that is hopefully illuminating:

>>> def only_assign(object):
...   x = 3
...   object = x
... 
>>> def mutate(object):
...   object.attribute = 3
... 
>>> class A:
...   pass
... 
>>> a = A()
>>> a
<__main__.A object at 0x7f54c3e256a0>
>>> only_assign(a)
>>> a
<__main__.A object at 0x7f54c3e256a0>
>>> mutate(a)
>>> a.attribute
3

Thank you so much! So, does this mean any assignments inside a caller function would not mutate the object but changes to the data members (for a class) will?
@GowthamGanesh Yes. Assigning to a data member is, by definition, a mutation of that object. As long as a reference to the object survives somewhere, that change will be reflected in the object. If no references to the object survive after the function leaves scope, the object is garbage collected.

Adil Baaj · Accepted Answer · 2016-09-20 23:48:48Z

I believe this is due to the fact that by doing :

node = self._Node(val)

in the _insert function you are not changing the value of the left/right node but binding the name node to a new _Node object, thus letting the left/right node as None.

On your second draft you are effectively affecting a new object to left / right node.

Here's a simple example to illustrate what happens on your code.

Guess what the print(test) will display?

test = [5, 5, 5]

def function(list):
   list[0] = 10
   list = range(1, 3)

function(test)
print test

If you think it will display [1,2] you're wrong .. it will actually display [10, 5, 5] because when doing list = range(1, 3) we are binding the name list to another object and not changing the first object it was bound to (the one test is actually bound to)

Collectives™ on Stack Overflow

Python: passing parameters over functions

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related