isSorted.hs

data Tree = Leaf | Node Int Tree Tree deriving Show

leftmost Leaf x = x
leftmost (Node x Leaf _) _ = x
leftmost (Node v (Node x y z) _) _ = leftmost (Node x y z) v

rightmost Leaf x = x
rightmost (Node x _ Leaf) _ = x
rightmost (Node v _ (Node x y z)) _ = rightmost (Node x y z) v

sorted Leaf = True
sorted (Node x Leaf Leaf) = True
sorted (Node x (Node y z t) Leaf) = (y<=x) && ((rightmost (Node y z t) x) <= x) && (sorted (Node y z t))
sorted (Node x Leaf (Node y z t)) = (x<y) && ((leftmost (Node y z t) x) > x) && (sorted (Node y z t))
sorted (Node x (Node a b c) (Node d e f)) = (a<=x) && (x>d) && ((rightmost (Node a b c) x) <= x) && ((leftmost (Node d e f) x) > x)  && (sorted (Node a b c)) && (sorted (Node d e f))

Use as-pattern to not repeat code and to avoid accidental mistakes. For example:
rightmost (Node v _ tr@(Node x y z)) _ = rightmost tr v