CODEWITHSUNDEEP
pythonbinary-search-tree
LeGOATJames23
LeGOATJames23

Reputation: 121

Python Binary Search Tree: Search function error

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?

Upvotes: 0

Views: 69

Answers (1)

LeGOATJames23
LeGOATJames23

Reputation: 121

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)

Upvotes: 1

Related Questions