Driver method that performs the actual traversal of input and calls the appropriate `resolver_method` when
        to perform the resolution.

        :param input: Any primitive type  (dict, array, string etc) whose value might contain an intrinsic function
        :param resolution_data: Data that will help with resolution. For example, when resolving parameter references,
            this object will contain a dictionary of parameter names and their values.
        :param resolver_method: Method that will be called to actually resolve an intrinsic function. This method
            is called with the parameters `(input, resolution_data)`.
        :return: Modified `input` with intrinsics resolved

def _traverse(self, input, resolution_data, resolver_method):
        """
        Driver method that performs the actual traversal of input and calls the appropriate `resolver_method` when
        to perform the resolution.

        :param input: Any primitive type  (dict, array, string etc) whose value might contain an intrinsic function
        :param resolution_data: Data that will help with resolution. For example, when resolving parameter references,
            this object will contain a dictionary of parameter names and their values.
        :param resolver_method: Method that will be called to actually resolve an intrinsic function. This method
            is called with the parameters `(input, resolution_data)`.
        :return: Modified `input` with intrinsics resolved
        """

        # There is data to help with resolution. Skip the traversal altogether
        if len(resolution_data) == 0:
            return input

        #
        # Traversal Algorithm:
        #
        # Imagine the input dictionary/list as a tree. We are doing a Pre-Order tree traversal here where we first
        # process the root node before going to its children. Dict and Lists are the only two iterable nodes.
        # Everything else is a leaf node.
        #
        # We do a Pre-Order traversal to handle the case where `input` contains intrinsic function as its only child
        # ie. input = {"Ref": "foo}.
        #
        # We will try to resolve the intrinsics if we can, otherwise return the original input. In some cases, resolving
        # an intrinsic will result in a terminal state ie. {"Ref": "foo"} could resolve to a string "bar". In other
        # cases, resolving intrinsics is only partial and we might need to continue traversing the tree (ex: Fn::Sub)
        # to handle nested intrinsics. All of these cases lend well towards a Pre-Order traversal where we try and
        # process the intrinsic, which results in a modified sub-tree to traverse.
        #

        input = resolver_method(input, resolution_data)

        if isinstance(input, dict):
            return self._traverse_dict(input, resolution_data, resolver_method)
        elif isinstance(input, list):
            return self._traverse_list(input, resolution_data, resolver_method)
        else:
            # We can iterate only over dict or list types. Primitive types are terminals
            return input