Probably true you are on his side (typical sideyards for buildings are 5 feet minimum) though it would be appropriate for a land surveyor to locate the property lines and even create a map of the fence, garage, and your drive - get your neighbor's permission for your surveyor to be on their property.  

There are some instances where fences can be considered to constitute line, although perhaps your neighbor was avoiding the tree.  If the tree was not a line tree, that is it was entirely on your neighbor's side, there are ways to estimate the value of the tree (i.e. http://www.sufa.com/appraisals.html), you'll have to agree with your neighbor on the appropriate approach.  If they wanted it taken out, determine the value of the timber, if they wanted it to stay, determine the replacement cost.  As for your driveway, if you need it on their side, you may have to get an ingress/egress easement.  

You may generate more responses in the Civil/Environmental forum.  Godd luck.