Implement an O(log n) Foldable.elem for binary search trees in Haskell

Consider the following definition for binary trees:

data Tree a = Nil | Node (Tree a) a (Tree a)

The Foldable instance can be defined as follows:

instance Foldable Tree where
  foldr _ z Nil = z
  foldr f z (Node l d r) = foldr f (f d (foldr f z l)) r

But the problem is that the elem function runs in O(n) rather than O(log n). When I try to implement a custom elem:

elem x Nil = False
elem x (Node l d r)
  | x == d = True
  | x < d = elem x l
  | otherwise = elem x r

I get Could not deduce (Ord a) arising from a use of ‘<’. How can this problem be fixed?