I would like to inquire about the scope in Python of an object that is a class variable.

import numpy as np


class treeNode:
    def __init__(self,key):
        self.leftChild = None
        self.rightChild = None
        self.value = key


def insert(root,key):
    if root is None:
        return treeNode(key)
    else:
        if root.value == key:
            return root
        elif root.value<key:
            root.rightChild = insert(root.rightChild,key)
        else:
            root.leftChild = insert(root.leftChild,key)
    return root

def insert_1(root,key):
    if root is None:
        root = treeNode(key)
    else:
        if root.value<key:
            insert_1(root.rightChild,key)
        elif root.value>key:
            insert_1(root.leftChild,key)

def construct_tree(a):
    def insert_1(root,key):
        if root is None:
            root = treeNode(key)
        else:
            if root.value<key:
                insert_1(root.rightChild,key)
            elif root.value>key:
                insert_1(root.leftChild,key)

    root = treeNode(a[0])
    for k in a:
        insert_1(root,k)

    return root

if __name__ == '__main__':

    np.random.seed(1)
    a = np.random.rand(12)

    tree = treeNode(a[0])
    for k in a:
        insert(tree,k)

    for k in a:
        insert_1(tree,k)


    tree_1 = construct_tree(a)

The insert() function produces the whole tree while insert_1() and construct_tree() which do not return anything fail to do so. Is there a function to recursively construct the whole tree without using a return statement? Thank you very much.

CodePudding user response：

In insert, the base case of the recursion is when you're inserting into an empty subtree, represented by None being passed in as root. It works because you can create and return a new treeNode in that case, and the caller will do the right thing with the return value.

If you don't want to be using return, you need to push that base case up to the calling code, so it avoids making a call when a leaf node is going to be added:

def insert_no_return(root, key):
    assert(root != None) # we can't handle empty trees

    if root.key == key:
        return # no value here, just quit early
    elif root.key < key:
        if root.rightChild is None:                 # new base case
            root.rightChild = treeNode(key)
        else:
            insert_no_return(root.rightChild, key)  # regular recursive case, with no assignment
    elif root.key > key:
        if root.leftChild is None:                  # new base case for the other child
            root.leftChild = treeNode(key)
        else:
            insert_no_return(root.leftChild, key)   # no assignment here either

That's a bit more repetitive than the version with return, since the base case needs to be repeated for each possible new child, but the recursive lines are a bit shorter since they don't need to assign a value anywhere.

As the assert says at the top, you can't usefully call this on an empty tree (represented by None), since it has no way to change your existing reference to the None root. So construct_tree probably needs special logic to construct empty trees. Your current version of that function doesn't handle empty input at all (and redundantly tries to add the root value to the tree a second time):

def construct_tree(a):
    if len(a) == 0:     # special case to construct an empty tree
        return None

    it = iter(a)        # use an iterator to avoid redundant insertion of a[0]
    root = treeNode(next(it))
    for k in it:
        insert_no_return(root, k)