def problem_4_5(tree):
    """ Write an algorithm to find the ‘next’ node (i.e., in-order successor)
    of a given node in a binary search tree where each node has a link to its
    parent.

    Solution: There are two cases:
    1. the node has a right subtree, in which case his immediate successor is
    the smallest node in the right subtree.
    2. if the node has an empty right subtree, then go up the ancestors until
    you reach a right one. If you reach the root, then the node has no successor
    because it's the max node.
    """
    def get_min(node):
        if node.left == None:
            return node
        return get_min(node.left)

    def successor(node):
        if node.right != None:
            return get_min(node.right)
        while node != None:
            if node.parent.left == node:
                return node.parent
            node = node.parent
        return None

    return successor(tree)