One of the most common communication patterns in sensor networks is routing data to a base station, while the base station can be either static or mobile. Even in static cases, a static spanning tree may not survive for a long time due to failures of sensor nodes. In this paper, we present an adaptive spanning tree routing mechanism, using real-time reinforcement learning strategies. We demonstrate via simulation that without additional control packets for tree maintenance, adaptive spanning trees can maintain the “best” connectivity to the base station, in spite of node failures or mobility of the base station. And by using a general constraint-based routing specification, one can apply the same strategy to achieve load balancing and to control network congestion effectively in real time.