The last attempt is wrong. It doesn't check the values in a perfect tree. For example,

Code:
        4
     2      6
   1   8  5   7
will be considered sorted, and it is not!