A method of encoding a video based on a bit depth increment, the method including: determining a scaling method so that a dynamic range, which is based on a bit depth of a restored image decreased by de-scaling that is performed to decrease the bit depth increment, is identical to a dynamic range based on a bit depth of an input image, and generating an internal image having the bit depth increment by applying the scaling method to pixel values of the input image; and determining and encoding coding units having a tree structure, for each maximum coding unit of the internal image having the bit depth increment.