Nitpick: I'd rename those fields: additions and removals. A field should be a noun, and verbes should be used for functions

this is part of the JSON schemas we agreed upon. If you don't mind we can add this as an extra task later.

Nitpick: Just for clarity, I'd rename that one resolveShapeUpdateMutation and the other one resolveTextUpdateMutation.

Wouldn't this one be better in the MobileSegmentExt.kt file?

Nitpick: I'd rename that isLastFullSnapshotTime

Nitpick: expectedAdditions

Nitpick: expectedRemovals

Here you're rewriting the prod algorithm, meaning that your test isn't really testing anything…
Another approach for this would be to start from the expected output: a list of nodes, and build a random tree that would give this output.
A pseudo algorithm would be:

fun generateTreeFromList(nodes : List<Node>) : Node {
    val maxDepth = 9 // from your current test
    val lastSiblings = Array<Node?>(size = maxDepth) { null }
    val tree = nodes.popFirst()
    while (nodes.isNotEmpty()) {
        // get random index of non null node from lastSiblings > 0
        val index = magic() // exercise left to reader
        val parent = lastSiblings[index - 1]
        val node = nodes.popFirst()
        parent.addChild(node)
        lastSiblings[index] = node
        for (i in (index + 1) until maxDepth) {
            lastSiblings[i] = null
        }
    }

    return tree
}