0

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


  • You're comparing a list with a int. If you want to check if the int is in the list, use the `in` keyword or define your own magic methods – 12944qwerty Dec 13 '21 at 03:27

0 Answers0