A video decoding method and apparatus and a video encoding method and apparatus based on a scanning order of hierarchical data units are provided. The decoding method includes: receiving and parsing a bitstream of an encoded video; extracting from the bitstream information about a size of a maximum coding unit for decoding a picture of the encoded video, and encoding information about a coded depth and an encoding mode for coding units of the picture, wherein the size of the maximum coding unit is a maximum size of a coding unit which is a data unit for decoding the picture; and determining a hierarchical structure of the maximum coding unit and the coding units into which the picture is divided according to depths, and decoding the picture based on the coding units, by using the information about the size of the maximum coding unit and the encoding information about the coded depth and the encoded mode.