Recently, my sewer line was backing up because the roots of the Rhus tree on on the footpath outside my house had penetrated the sewer pipe. Council wanted the tree to remain.
So the solution we adopted was to have a specialist drainer cut away the roots and install a plastic pipe within the old clay pipes. It was not cheap – $11,000, but it solved the problem. It was cheaper than removing the old pipes and installing new ones. The sewer no longer backs up and the tree continues to flourish.
My suggestion is to obtain a quotation, and ask the OC next door to go halves.