Finding Inorder Predecessor of a node in a BST:

Algorithm:

1. If right subtree of a node is NOT NULL, return the MIN element from the right subtree
2. If right subtree of a node is NULL, return the deepest ancestor of a node where it comes from the left.

def inorder_pre(root,node):
    temp = None
    if node.left:
        temp = node.left
        while temp.right != None:
            temp = temp.right
        return temp

    #If right subtree is null
    currentNode = root
    ancestors = []
    while currentNode:
        if currentNode.data == node.data:
            return ancestors[-1]
        if currentNode.data > node.data:
            currentNode = currentNode.left
        else:
            ancestors.append(currentNode.data)
            currentNode = currentNode.right