recursive class definition in python

Question

Sorry if my English is bad, I speak Korean as mother tongue.
I am implementing binary search tree in Python 3, but I wasn't able to meet my goal.
Here is code:

class Node(object):

    def __init__(self, key=None, data=None):
        self.key = key
        self.data = data

class BinarySearchTree(object):
    keyfunc = None  # Will it be worse when using lambda x: x as default?
    
    def __init__(self, node=None):
        self.root = node
        self.left = None
        self.right = None
        # I don't want default to be NoneType, but don't know how for now.

    def add(self, key, data=None):
        node = Node(key, data)
        if self.root is None:
            self.root = node
            return
        parent = self.root.key
        if self.keyfunc is None:
            if key < parent:
                if self.left is None:
                    self.left = __class__(node)
                else:
                    self.left.add(key, data)
                        
            elif key > parent:
                if self.right is None:
                    self.right = __class__(node)
                else:
                    self.right.add(key, data)
        else:
            if keyfunc(key) < keyfunc(parent):
                if self.left is None:
                    self.left = __class__(node)
                else:
                    self.left.add(key, data)
            elif keyfunc(key) > keyfunc(parent):
                if self.right is None:
                    self.right = __class__(node)
                else:
                    self.right.add(key, data)
    def inorder(self):
        if self.root:
            if self.left:
                self.left.inorder()
            print(self.root.key, end=' ')
            if self.right:
                self.right.inorder()

if __name__ == '__main__':
    bst1 = BinarySearchTree()
    arr = [2,6,4,3,2,7,8,1,9,5]
    for key in arr:
        bst1.add(key)
    bst1.inorder()

It works anyway, but what I want is:

• even when root node has no child, I want the type of bst1.left(or bst1.right) be always BinarySearchTree.
  That way, I can allow null tree treated in consistency with other trees, and also can I remove repeating if self.left is None in add().
• I don't want to manually do bst1.left = BinarySearchTree(None) after class definition, because it will be required to applied to all of nodes.

I tried self.left = BinarySearchTree(None)(of course it resulted bad recursion), and tried to use __new__() method and Metaclasses as answered in other stackoverflow questions, but couldn't come up with solution.
It would very grateful if I can get help.

Answer 1

Consider replacing NoneType child trees with an empty tree object with a None root. Also, to answer the question in your code comment, I think defaulting keyfunc = lambda x: x is reasonable, and it simplifies your code further.

class BinarySearchTree:
    def __init__(self, node, keyfunc=lambda x: x):
        self.root = node
        self.keyfunc = keyfunc
        if node is not None:
            self.left = self.new_empty()
            self.right = self.new_empty()

    def new_empty(self):
        """Create a new empty child for this tree"""
        return BinarySearchTree(None, self.keyfunc)
    
    def add(self, key, data=None):
        node = Node(key, data)
        if self.root is None:
            self.root = node
            self.left = self.new_empty()
            self.right = self.new_empty()
        else:
            parent = self.root.key
            if self.keyfunc(key) < self.keyfunc(parent):
                self.left.add(key, data)
            elif self.keyfunc(key) > self.keyfunc(parent):
                self.right.add(key, data)

    def inorder(self):
        if self.root is not None:
            self.left.inorder()
            print(self.root.key, end=' ')
            self.right.inorder()

For ease of use, you may also choose to add a definition like the following:

def __bool__(self):
    return self.root is not None

This lets you simplify a test to see if a node is empty by doing something like if self: instead of if self.root is not None: in the inorder method or if self.left: to see if there is a left child tree instead of if self.left.root is not None:.