As the next generation standard of video coding, the High Efficiency Video Coding (HEVC) achieves significantly better coding efficiency than all existing video coding standards. A Coding Unit (CU) quad tree concept is introduced to HEVC to improve the coding efficiency. Each CU node in quad tree will be traversed by depth first search process to find the best Coding Tree Unit (CTU) partition. Although this quad tree search process can obtain the best CTU partition, it is very time consuming, especially in interframe coding. To alleviate the encoder computation load in interframe coding, a fast CU depth decision method is proposed by reducing the depth search range. Based on the depth information correlation between spatio-temporal adjacent CTUs and the current CTU, some depths can be adaptively excluded from the depth search process in advance. Experimental results show that the proposed scheme provides almost 30% encoder time savings on average compared to the default encoding scheme in HM8.0 with only 0.38% bit rate increment in coding performance.