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.

Please see this Q&A on the topic. You should find it very helpful. If you have follow-up questions, I am here to help. — Mulan
– Mulan, Commented Apr 28, 2021 at 15:37
@Thankyou that Q&A is very interesting. Thank you for introducing me that. — k9wan
– k9wan, Commented Apr 29, 2021 at 13:53

user108471 · Accepted Answer · 2021-05-22 02:17:33Z

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:.

edited May 22, 2021 at 2:17

answered Apr 27, 2021 at 15:06

user108471

2,6174 gold badges30 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

k9wan Over a year ago

the conditional if node is not None: really helped me. I'm surprised I couldn't come up with that conditional. maybe my thought got stiff. thanks so much! by the way, I had mistake; keyfunc(key) had to be __class__.keyfunc(key).

user108471 Over a year ago

@k9wan Ah, I had overlooked that the keyfunc = lambda x: x line was in the class definition and not in module scope, where that would have worked. I have updated the answer with a possible implementation that accepts the keyfunc as a parameter, which is how I would probably do it.

Collectives™ on Stack Overflow

recursive class definition in python

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related