Реализуйте serialize(root) → string и deserialize(string) → root. Должно работать для любого, в т.ч. несбалансированного и неполного дерева.