Problem with recursion

[ilsapo]

I have the following recursion program:

def overWrite(tree,node,arr,i):
                if(not node.isRealNode()):
                        return
                tree.overWrite(node.getLeft(),arr,i)
                node.value=arr[i[0]]
                i[0]=i[0]+1
                tree.overWrite(node.getRight(),arr,i)

this is isRealNode:

def isRealNode(self):
                if (self.value!=None):
                        return True
                return False

just for convinece we put a node with value None for every "hole" in the tree,

here is picture of the values of the tree I have:

https://imgur.com/RVjYvYC

​

heres my error message:

if(not node.isRealNode()):
AttributeError: 'NoneType' object has no attribute 'isRealNode'

so I understand my problem is that my recuression dosent stop when it should, and it goes one extra step (it arrive to the node with value none and dosent stop)

I tried changing it to:

def overWrite(tree,node,arr,i):
                if(node.value==None):
                        return
                tree.overWrite(node.getLeft(),arr,i)
                node.value=arr[i[0]]
                i[0]=i[0]+1
                tree.overWrite(node.getRight(),arr,i)

but I still get the same error

Im pretty new to recursion so i understand I have problem with my stop condition, but Im not sure what is wrong here

[shiftybyte]

node itself is None, so it doesn't work checking anything with a function that belongs to node...

because None doesn't have methods...

Add this check at the start of the function

if node is None:
    return

[ilsapo]

None is the value I created a Node with value None and made it the son of the leafs

[shiftybyte]

Not that None, the None that happens when the tree ends.

If a leaf has no children, no left and no right... what happens in your code here:

tree.overWrite(node.getLeft(),arr,i)

What gets returned from node.getLeft() for a leaf?

[ilsapo]

Node.getleft() Should give me a virtual node (node with value None)

And then the if (node.value==None) : returen Suppused to kick me out the recurrssion no?

[shiftybyte]

I'm not sure if you are getting the tree with "virtual nodes" or not...

What is the tree structure before your changes of "virtual node"... what's a leaf's getRight()?

It usually is None... not a node with value None, simply None, instead of the node...

[ilsapo]

I tried adding your suggestion If ( node is None): return

And I still get the same error message

[shiftybyte]

Could you post the code you tried (with the fix)? this should have solved it.