data Tree a = Empty
            | Node (Tree a) a (Tree a) deriving Show

singleton :: a -> Tree a
singleton x = Node Empty x Empty

-- Return tree with all elements replaced by given value
ofShape :: Tree a -> a -> Tree a
ofShape Empty           _ = Empty
ofShape (Node lt _ rt)  x = Node (ofShape lt x) x (ofShape rt x)

-- Helper function does the following
--
-- Input :: a value x and a tree t
--
-- Output :: a tuple (t',m) where t' is a tree of the same shape as t but with
--           x at each of the nodes, and m is the maximum of all elements in t
--
helper :: Int -> Tree Int -> (Tree Int, Int)
helper _ Empty          = (Empty, 0)
helper x (Node lt u rt) = (Node ls x rs, lmax `max` u `max` rmax)
  where (ls,lmax) = helper x lt
        (rs, rmax)= helper x rt

onePass :: Tree Int -> Tree Int
onePass t = tx
     where (tx, mx) = helper mx t

mytree :: Tree Int
mytree = Node (singleton 8) 4 (Node (singleton 5) 2 (singleton 1))