Why did you conclude that you failed because of that? That sounds like a pass with flying colors. Did you specifically get feedback about that segment?
In the few remaining minutes after we agreed that it was possible to correctly deserialize a tree serialized in this way, I did not produce a linear time deserializer.