It could be Tabebuia rosea. The leaf looks similar to it. I don't have it, but have it in our workplace campus and is planted in many roadsides, here and there. It usually blooms in December here at a time when the plant has shed all its leaves. After flowering the new leaves appear. This pic was taken in 2006 December. I guess from the description and photos malabajaj has sent, this is the one. Yes. without flowers it would be hard to pin-point.
Mala Bajaj. 
