There are two botanical gardens, one of them, Jardim Botânico da Ajuda, is just behind the unfinished Palace. Leave the palace through its anticlimactic western gate, cross the street and turn left, down towards the river. The entrance to the garden is after a few dozen meters on the right side.
Again it was the wrong time for blossoms, but at least this tree was worth going in.