How to obtain the parent of a collection using Python
The best I could come up with so far is a recursion that searches for the parent collection. Note that this is not a particularly efficient solution but at least it solves my problem. The code looks as follows:

import bpy


def get_parent_collection_names(collection, parent_names):
  for parent_collection in bpy.data.collections:
    if collection.name in parent_collection.children.keys():
      parent_names.append(parent_collection.name)
      get_parent_collection_names(parent_collection, parent_names)
      return


def turn_collection_hierarchy_into_path(obj):
  parent_collection = obj.users_collection[0]
  parent_names      = []
  parent_names.append(parent_collection.name)
  get_parent_collection_names(parent_collection, parent_names)
  parent_names.reverse()
  return '\\'.join(parent_names)


obj = bpy.context.view_layer.objects.active
print(turn_collection_hierarchy_into_path(obj))


This code will print out the collection hierarchy of the selected object as a Windows style path (backslash as separator).

Note that objects can be part of multiple collections which means you can actually create a graph, not just a tree. The above code will simply ignore that fact and just pick the first collection that the object is part of.