pythonalgorithmdata-structuresbinary-search-tree

Binary Search tree python. Iterative search


I was wondering if someone could help me see what i am doing wrong with this search function for a binary search tree. Have to use the iterative version due to the size of data. I keep getting stuck in an infinite while loop when i print out values for debugging. Thanks!

I also get this error:

while (word_search.value != user_input) and (word_search.value != None):
    AttributeError: 'NoneType' object has no attribute 'value'

    def iterative_word_search(current, user_input):
            word_search = current.root
            print("User input value", user_input)
            print("Word Search Value", word_search.value)

            while (word_search.value != None) and (word_search.value != user_input):
                print("While Loop value: ", word_search.value)      
                if(user_input < word_search.value):
                  word_search = word_search.left
    #              print("If statement value: " ,word_search.value)
                elif(word_search.right != None):
                  word_search = word_search.right
                  print("Else statement value: ", word_search.value)
                elif(word_search.value == None):
                    print("Word does not exist")
                    return word_search
            return word_search

Solution

  • You need to assert that left and right are not None before calling .value on them:

    Python lazy evaluation of expressions allows you to do this on one line. if word_search is None or word_search.value is None will evaluate word_search, and if it is None, will not evaluate word_search.value.

    def iterative_word_search(current, user_input):
    
        word_search = current.root
    
        while True:
            if word_search is None or word_search.value is None:
                print("not found")
                break
            if word_search.value == user_input:
                print("found")
                break
            if(user_input < word_search.value):
                word_search = word_search.left
            elif(word_search.right != None):
                word_search = word_search.right
    
        return word_search