Optimal BST challenge
Use the properties of a BST

In a BST, if the value being search for is less than the key of the current node, then it is in the left subtree and if the value is greater than the key of the current node, then it is in the right subtree.  Your code always searches the left subtree first and then searches the right subtree if needed.  This code only searches one subtree:

def pathToNode(node, path, k):
    path.append(node.key) 
    if node.key == k : 
        return True

    elif k &lt; node.key:
        if node.left and pathToNode(node.left, path, k):
           return True

    else:
        if node.right and pathToNode(node.right, path, k): 
           return True

    path.pop() 
    return False


The same applies to getlevel().

distance() determines the path from the root to each node. Then determines the common prefix of each path. This can be simplified as observing that if both nodes are in the same subtree, then the root of the current tree isn't on the path between the nodes.

def distance(node, x, y):
    if x &lt; node.key and y &lt; node.key:
        return distance(node.left, x, y)

    elif node.key &lt; x and node.key &lt; y:
        return distance(node.right, x, y)

    else:
        path1 = []
        pathToNode(node, path1, x) 
        path2 = [] 
        pathToNode(node, path2, y)

        return len(path1) + len(path2) - 2


Note: you don't actually need the path of a node, just it's depth.