Python Binary Search Tree: Search function error

Question

class Node: 
    def __init__(self, key, parent = None): 
        self.key = key
        self.parent = parent 
        self.left = None 
        self.right = None
        if parent != None:
            if key < parent.key:
                parent.left = self
            else:
                parent.right = self

    def search(self, key):
        if self == None:
            return (False, None)
        if self.key == key:
            return (True, self)
        elif self.key > key:
            return self.left.search(key)
        elif self.key < key:
            return self.right.search(key)
        else:
            return (False, self)

t1 = Node(25)
t2 = Node(12, t1)
t3 = Node(18, t2)
t4 = Node(40, t1)

print('-- Testing search -- ')
(b, found_node) = t1.search(18)
assert b and found_node.key == 18, 'test 8 failed'
(b, found_node) = t1.search(25)
assert b and found_node.key == 25, 'test 9 failed'
(b, found_node) = t1.search(26)
assert(not b), 'test 10 failed'
assert(found_node.key == 40), 'test 11 failed'


Traceback (most recent call last):
  File "/Users/user/PycharmProjects/practice/main.py", line 50, in <module>
    (b, found_node) = t1.search(26)
  File "/Users/user/PycharmProjects/practice/main.py", line 27, in search
    return self.right.search(key)
  File "/Users/user/PycharmProjects/practice/main.py", line 25, in search
    return self.left.search(key)
AttributeError: 'NoneType' object has no attribute 'search'

My search function is getting an error with the recursive calls to search(self.left, key) and search(self.right, key). It says search() takes 2 positional arguments, but is getting 3, and I am not understanding how this is happening?

Try Node.search(self.left, key) and Node.search(self.right, key). Since you're invoking the search method of the self instance, the self instance gets passed implicitly as the first argument. — Paul M.
– Paul M., Commented Nov 14, 2022 at 18:47
Make a minimal reproducible example that constructs a few nodes and creates the error when calling Search. — Mark Tolonen
– Mark Tolonen, Commented Nov 14, 2022 at 18:47
You should be saying self.left.search(key). Remember that calling self.search supplies self as the automatic first parameter. — Tim Roberts
– Tim Roberts, Commented Nov 14, 2022 at 18:47
What if the parent already has a left or right key? The parent should be in charge of adding a new node to its (possibly empty) left or right child as appropriate, rather than the node trying to insert itself. — chepner
– chepner, Commented Nov 14, 2022 at 20:29
self will never be None, unless you unconventionally call Node.search directly rather than via an instance of Node. When self.left is None, self.left.search(...) is an AttributeError, not the same as Node.search(None, ...). — chepner
– chepner, Commented Nov 14, 2022 at 20:31

LeGOATJames23 · Accepted Answer · 2022-11-14 20:25:31Z

1

I really had a brain fart with this question.... Thank you to those commenting reminding me the function is being called with the self instance being passed implicitly, I forgot basics of objects i guess lol. This implementation passes the test cases. If there is a better way of implementing this, feel free to post, as I would love to see them...

def search(self, key):
    if self == None:
        return (False, self)
    if self.key == key:
        return (True, self)
    elif self.key > key:
        if self.left == None:
            return (False, self)
        else:
            return self.left.search(key)
    else:
        if self.right == None:
            return (False, self)
        else:
            return self.right.search(key)

answered Nov 14, 2022 at 20:25

LeGOATJames23

1218 bronze badges

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

Collectives™ on Stack Overflow

Python Binary Search Tree: Search function error

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related