Gowtham Ganesh Gowtham Ganesh - 2 months ago 4
Python Question

Python: passing parameters over functions

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!

Answer

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