Ultrasound Elastography is an emerging imaging technique that allows estimation of the mechanical characteristics of tissue. Two issues that need to be addressed before widespread use of elastography in clinical environments are real time constraints and deteriorating effects of signal decorrelation between pre- and post-compression images. Previous work has used Dynamic Programming (DP) to estimate tissue deformation. However, in case of large signal decorrelation, DP can fail. In this paper we, have proposed a novel solution to this problem by solving DP on a tree instead of a single Radio-Frequency line. Formulation of DP on a tree allows exploiting significantly more information, and as such, is more robust and accurate. Our results on phantom and in-vivo human data show that DP on tree significantly outperforms traditional DP in ultrasound elastography.