def predecessor_inorder(bst, node):
    """
    Cases:
    1. Node has a left subtree - predecessor is the maximum in the left subtree (LEFT, ROOT(node))
    2. Node does not have a left subtree.  Node lies in the right subtree of its predecessor (ROOT, RIGHT(node))
        To find predecessor, keep going up till the node is a right child of its parent. Then parent node is the
        predecessor.
    """
    if node.left is not None:
        return bst.maximum(node.left)
    y = node.parent
    while y is not None and y.left == node:  # not right
        node = y
        y = y.parent
    return y