I am currently studying for data structures exam and am trying to understand my error here while ... So I am working on Binary Search Tree practice and so i created a search function to validate that a element is indeed in my binary search tree. When calling the search function with a value in my BST, my code returns "None" but am not sure why. If possible, can you please explain to me, i am sure its a silly mistake I am doing...
#############################
# Binary Search Tree Youtube Practice
#############################
# Binary search tree is a recursive Data Structure
class BinarySearchTreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def add_child(self,data):
if data == self.data: # checking to see if the item is already in the binary tree
return
if data < self.data:
# add data value in left subtree
if self.left:
self.left.add_child(data)
else:
self.left = BinarySearchTreeNode(data)
else:
# add value to right subtree
if self.right:
self.right.add_child(data)
else:
self.right = BinarySearchTreeNode(data)
def in_order_traversal(self):
elements = []
# visit left tree
if self.left:
elements += self.left.in_order_traversal()
# visit base node
elements.append(self.data)
# visit right tree
if self.right:
elements+= self.right.in_order_traversal()
return elements
def search(self,value):
if self.data == value:
return True
if value < self.data:
# value might be in left subtree
if self.left:
self.left.search(value)
else:
return False
if value > self.data:
# value might be in right subtree
if self.right:
self.right.search(value)
else:
return False
def build_tree(elements):
root = BinarySearchTreeNode(elements[0])
for i in range(1,len(elements)):
root.add_child(elements[i])
return root
if __name__ == '__main__':
numbers = [17,4,1,20,9,23,18,34,18,4]
numbers_tree = build_tree(numbers)
print(numbers_tree.in_order_traversal())
print(numbers_tree.search(20)) # returns None