How to resolve a 'NoneType Error' on my code?

Question

I'm trying to make a binary tree deletion code on python. In some reason, I got an error 'AttributeError: 'NoneType' object has no attribute 'right''.

When I tried to print the type of variable 'root', it says <class 'NoneType'>.

Also when I changed the 'root = None insert(root, 50)' to 'root = Node(50)', it worked.

I'm guessing that there is some error on Class Definition or insert function. Can anybody help me?

import random
from timeit import default_timer as timer


class Node(object):
    def __init__(self, key, parent=None):               
        self.key = key
        self.left = None
        self.right = None
        self.parent = parent


def insert(node, key):
    if node is None:
        node = Node(key)
        return node
    elif key < node.key:
        node.left = insert(node.left, key)
        node.left.parent = node
    else:
        node.right = insert(node.right, key)
        node.right.parent = node
    return node


def delete(node):
    if node.parent is None:
        node = delete_node(node)    # root
    elif node == node.parent.left:
        node.parent.left = delete_node(node)
    else:
        node.parent.right = delete_node(node)


def delete_node(r):
    if r.left is None and r.right is None:
        return None
    elif r.left is not None and r.right is None:
        return r.left
    elif r.left is None and r.right is not None:
        return r.right
    else:
        s = r.right
        while s.left is not None:
            sparent = s
            s = s.left
        r.key = s.key
        if s == r.right:
            r.right = s.right
        else:
            sparent.left = s.right
        return r


root = None
insert(root, 50)
insert(root, 99)
insert(root, 78)
insert(root, 57)
insert(root, 80)
insert(root, 4)
insert(root, 64)
insert(root, 35)
insert(root, 58)
insert(root, 33)

print(root.right.left.key)
start = timer()
delete(root.right.left)
print(timer() - start)
print(root.right.left.key)

Answer 1

The insert function creates the first node if it doesn't exist, but you ignore the return value. Instead, you should reassign it to node: root = insert(root, 50), etc.

Answer 2

You need to get the return type. If you reassign a variable in a function, it remains in the function scope. The variable is only mutated of it is already the object. That’s why your second example worked: you passed in a Node which was changed, while your first example didn’t: you created a Node and returned it.

You’ll want to reassign root in your first insert function.

root = assign(None, 50)
assign(root, 99)
…

As an aside, I often find it easier to split these functions into two. Your first one which returns a new Node might be called create, and you simply pass a value. After that you can call assign with the root node.

Answer 3

The problem has to do with the fact that when you assign a variable inside a function, that variable is edited locally, not globally. The easiest fix is to return the value from insert, delete, etc. instead of trying to assign it inside your functions:

def some_func(x):
    if x is None:
        return 1
    else:
        return x + 1

x = None
x = some_func(x)