scuwp:
If the tree is not overhanging then I am in the 'it's entirely your choice' camp. What I will add however is how much you want to get along with your neighbors. A mutual agreement may help in the long run, but come to a clear agreement on exactly what will be done, and who will pay. They have approached you in good faith so be kind back and see if you can come to an agreement you both can live with.
It may not be as simple as this. The pohutukawa is a native, it may be protected and you may need to get special permission to remove it or even prune it.