In this paper, a new reversible data hiding method based on a dual binary tree of embedding levels is proposed. Four neighborhood pixels in the upper, below, left and right of each pixel are used as reference pixels to estimate local complexity for deciding embeddable and non-embeddable pixels. The proposed method does not need to record pixels that might cause underflow, overflow or unsuitable for embedment. This can reduce the size of location map and release more space for payload. Experimental results show that the proposed method is more effective in increasing payload and improving image quality than some recently proposed methods.