#Chapter 45 Binary search tree (recursive)

def binaryTreeSearch(itemSought, currentNode):
    item = currentNode[1]
    left = currentNode[0]
    right = currentNode[2]
    print("left, item,right =",left,item,right)
    if item == None: #previous node was a leaf node
        print(currentNode)
        return False
    elif itemSought==item:
        return True
    elif itemSought<item:
        if left!=None:
            return binaryTreeSearch(itemSought, searchTree[left])
        else:
            return False
    else:
        if right!= None:
            return binaryTreeSearch(itemSought, searchTree[right])
        else:
            return False
    #endif
#endsub

#main
searchTree=[[1,17,4],    
            [2,8,6],
            [None,4,7],
            [None,14,None],
            [5,22,8],
            [None,19,None],
            [None,12,3],
            [None,5,None],
            [9,30,None],
            [None,25,None],
            [None,None,None]
            ]
nodeData = [17,8,4,14,22,19,12,5,30,25]
#left = [1,13,-1,-1,5,-1,-1,-1,9,-1]
key = int(input("Enter key to search for: "))
currentNode = searchTree[0]
item = binaryTreeSearch(key,currentNode)
if item ==True:
    print("item",key, "is in the list")
else:
   print("item is not in the list")