So, this works in Haskell

replaceMin :: Tree Int -> Tree Int
replaceMin t = let (t', m) = rpMin (t, m) in t'

rpMin :: (Tree Int, Int) -> (Tree Int, Int)
rpMin (Leaf a, m) = (Leaf m, a)
rpMin (Branch l r, m) = let (l', ml) = rpMin (l, m)
                            (r', mr) = rpMin (r, m)
                   in (Branch l' r', ml `min` mr)
And replaces every Leaf in the tree with the minimum value in the tree. All in one pass.

What other Voodoo magic can that dog do?

>>12
:set number CR