Python - Árbol de búsqueda

Un árbol de búsqueda binaria (BST) es un árbol en el que todos los nodos siguen las propiedades mencionadas a continuación: el subárbol izquierdo de un nodo tiene una clave menor o igual que la clave de su nodo principal. El subárbol derecho de un nodo tiene una clave mayor que la clave de su nodo principal. Por tanto, BST divide todos sus subárboles en dos segmentos; el subárbol izquierdo y el subárbol derecho y se puede definir como -

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Buscar un valor en un árbol B

La búsqueda de un valor en un árbol implica comparar el valor entrante con el valor que sale de los nodos. Aquí también atravesamos los nodos de izquierda a derecha y finalmente con el padre. Si el valor buscado no coincide con ninguno de los valores de exitign, devolvemos el mensaje no encontrado; de lo contrario, se devuelve el mensaje encontrado.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

# Insert method to create nodes
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
# findval method to compare the value with nodes
    def findval(self, lkpval):
        if lkpval < self.data:
            if self.left is None:
                return str(lkpval)+" Not Found"
            return self.left.findval(lkpval)
        elif lkpval > self.data:
            if self.right is None:
                return str(lkpval)+" Not Found"
            return self.right.findval(lkpval)
        else:
            print(str(self.data) + ' is found')
# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()


root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
print(root.findval(7))
print(root.findval(14))

Cuando se ejecuta el código anterior, produce el siguiente resultado:

7 Not Found
14 is found