def predecessor_preorder(bst, node):
    """
    Cases:
    1. If node is the left child of its parent, the predecessor of node is parent
    2. If node is the right child of its parent, predecessor is in the left subtree of its parent. This is the
        maximum in the left subtree of parent. If parent does not have a left subtree, then parent is the predecessor
    """
    if node.parent is None:  # node was root
        return None
    y = node.parent
    if y.left == None or y.left == node:
        return y
    y = y.left
    while y is not None:
        node = y
        y = y.right
    return node